Энрике Грасиан - Мир математики. т.3. Простые числа. Долгая дорога к бесконечности

* * *

ДИКОВИННЫЕ ЧИСЛА

Число 313 изображено на номерном знаке автомобиля Дональда Дака. Оно обладает любопытным свойством палиндрома: его можно читать слева направо и справа налево как в десятичной системе счисления, так и в двоичной. Это единственное трехзначное простое число с таким свойством: 313 (в десятичной системе) = 100111001 (в двоичной системе). Кроме того, число 100111001 в десятичной системе счисления является простым.

Существует много простых чисел со странными свойствами. Например, «репьюниты» (от repeated unit — «повторенная единица»), которые состоят из длинных последовательностей единиц. Число 11111111111111111111111 (двадцать три единицы) является простым. В принципе, это просто диковинки, хотя в один прекрасный день эти числа могут стать частью теоремы или гипотезы, имеющей некую ценность в математике. Еще одна любопытная последовательность основана на числе 91, которое является составным (91–13 x 7). Если в середину этого числа вставлять последовательности нулей и девяток, то полученные числа чередуются, являясь то простыми, то составными:

9901 — простое;

999001 — составное;

99990001-простое;

9999900001 — составное;

999999000001 — простое;

99999990000001 — составное;

9999999900000001 — простое;

999999999000000001 — составное.

К сожалению, следующее число 999999999990000000001 также является составным!

* * *

Мы видели, как математики, такие как Мерсенн, Ферма, а иногда даже сам Эйлер, искали практические инструменты для работы с числами. Это в некоторой степени подрывало становление строгой теории. Доказательства едва упоминались, но результаты продолжали использоваться. Гаусс начал новую эру в истории математики, настояв на том, что приведение строгих доказательств должно быть главной целью.

Тем не менее с простыми числами мы снова, казалось бы, опираемся на эмпирический подход. Мы используем недоказанные теоремы и полагаемся на результаты, если знаем, что вероятность ошибки очень мала. Мы действуем как Ферма, но даже не пытаемся прятать гипотетические доказательства. Мы можем так делать, потому что, во-первых, имеем огромные возможности благодаря компьютерным алгоритмам, а во-вторых — огромную потребность в больших простых числах.

В чисто теоретическом смысле можно сказать, что простые числа продолжают сопротивляться усилиям математиков. История их исследований в значительной степени является историей неудач. Наибольший успех был с дзета-функцией Римана, но мы все-таки понимаем, что это лишь частичный успех. Эйлер, который был великим математическим провидцем, не испытывал особенно оптимистичных чувств по поводу наших шансов понять эти неуловимые числа: «Математики уже давно тщетно пытаются найти закономерности в последовательности простых чисел, но у меня есть основания полагать, что это тайна, в которую человеческий разум никогда не сможет проникнуть».

Теорема утверждает, что любое натуральное число, отличное от 1, может быть единственным способом выражено в виде произведения простых чисел. Сначала мы должны объяснить, почему единица не считается простым числом.

Существует несколько причин, но наиболее очевидным является тот факт, что для числа 1 теорема не имеет места, так как оно может быть разложено на множители несколькими способами:

1 = 1 х 1 = 1 х 1 х 1 = 1 х 1 х 1 х 1 = …

С этой оговоркой мы можем доказать теорему в два этапа. Сначала покажем, что число может быть представлено в виде произведения, а затем — что это можно сделать единственным способом.

Первую часть докажем методом от противного. Предположим, что n является наименьшим числом, которое не может быть разложено на простые множители. Мы знаем, что это число не 1, потому что мы исключили такую возможность в формулировке теоремы. Не может оно быть и простым числом, так как тогда бы оно раскладывалось только на себя. Таким образом, это число должно быть составным вида n = а х Ь , где а и Ь меньше, чем n . Но так как n — это наименьшее число, которое не может быть разложено на простые множители, значит, а и b могут быть разложены на простые множители, что дает разложение и для n . Таким образом, мы пришли к противоречию.

Вторая часть доказательства опирается на следующий результат.

Если р — простое число, на которое делится произведение множителей, то на р обязательно должен делиться один из этих множителей. (Этот результат может быть доказан с помощью соотношения Безу.) Предположим, что натуральное число, большее 1, может быть разложено на простые множители двумя способами, тогда мы возьмем простое число р из первого разложения. На это число должно обязательно делиться второе разложение и, следовательно, один из его множителей.

А так как этот множитель — тоже простое число, он должен быть равен р . Таким образом, мы нашли два одинаковых множителя в разных разложениях. Повторяя процесс для любого другого простого числа из первого разложения, мы докажем, что оба разложения содержат одинаковый набор простых множителей.

В терминах теории сравнений, как в пятой главе, теорема формулируется так: «Если р — простое число, то для любого натурального числа а, а р a (mod р )». Это равносильно тому, что а р — а делится на р .

Докажем теорему с помощью метода индукции. Другими словами, мы предположим, что это верно для некоторого натурального числа а , и затем покажем, что это также верно для числа а + 1.

Начнем с предположения, что а р — а делится на р . Согласно биномиальному разложению Ньютона,

Перенося члены а р и 1 налево, мы получим:

Множитель р содержится во всех слагаемых в правой части, поэтому правая часть уравнения делится на р и, следовательно, левая часть ( а + 1) р — а р — 1 тоже делится на р.

Так как по индукции а р— а делится на р , то и следующая сумма также делится на р :

Эту сумму можно переписать в виде:

Следовательно, делимость на р верна и в случае а + 1, то есть теорема доказана.