Доказательство бесконечности простых чисел

Данное доказательство принадлежит Евклиду, и оно осуществляется уже известным нам методом от противного. Предположим, что вывод ложен и количество простых чисел конечно. Это означает, что существует самое большое простое число. Назовем его p_n. Теперь составим число N из произведения всех простых чисел плюс один: N = p₁p₂... p_n‑1p_n + 1 = A_n + 1. Такое число не делится ни на одно простое число от p₁ до p_n, поскольку тогда на них должно было бы делиться как A_n, так и 1, и ясно, что ни одно число не является делителем 1, кроме него самого. То есть либо N – простое число, либо оно содержит простые множители, большие p_n. Следовательно, мы нашли простое число, большее p_n, что противоречит нашей гипотезе о том, что p_n – самое большое простое число. Получается, гипотеза ложна и количество простых чисел бесконечно.  

Наконец, есть другие числа, тесно связанные с совершенными: так называемые дружественные числа. Два числа называются дружественными, когда сумма собственных делителей одного равна другому, и наоборот. В античности единственной известной парой дружественных чисел были 220 и 284. Действительно, собственные делители 220 – это 1,2,4,5,10,11,20, 22,44,55,110,а 284‑ 1 + 2 + 4+ 5+ 10 + 11 + 20 + 22 + 44 + 55 + 110. Аналогично, собственные делители 284 – это 1, 2, 4, 71, 142, а 220 ‑ 1 + 2 + 4 + 71 + 142.

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

Возрождение пифагорейского мистицизма в начале Нового времени поддерживало интерес к этим проблемам.

В книге "Трактат о всеобщей гармонии" Мерсенн утверждал, что Ферма открыл пару дружественных чисел, 17 296 и 18416, первую такую пару, обнаруженную со времен античности. Также, если верить данной книге, Ферма доказал, что как 120, так и 672 являются недостаточными числами, равными половине суммы их собственных делителей (эта сумма равна 240 и 1344 соответственно). Такие числа известны как мультисовершенные, или k‑совершенные.

[Среди] знатных людей... которые внесли вклад в эту область математики и которых никто не может научить ничему новому, я бы повторил имя... [Этьена Паскаля] и добавил бы имя господина Ферма...  

Комментарий Марена Мерсенна в книге "Трактат о всеобщей гармонии" (1636)

Итак, уже в 1636 году Ферма задумывался о том, как определить сумму собственных делителей заданного числа. На тот момент он уже явно знал, как это сделать. Его способ так и не был опубликован и сейчас утерян. Однако до нас дошел метод, которым мы обязаны Рене Декарту. Поскольку любое число может быть выражено в виде произведения степеней его простых множителей, N =p₁^k1p₂^k2...p_n^kn, собственные делители – это все возможные сочетания между данными множителями. Например, 1452 = 2² · 3 · 11², и его собственными делителями являются 2, 3, 11, 2², 11², 2 · 3, 2² · 3 и так далее, включая все сочетания. Декарт нашел формулу, которая на основе предыдущих результатов предлагала новый собственный делитель, пока все они не заканчивались. Это известно как рекурсивная формула. Метод Ферма явно аналогичный.

Математик получил несколько результатов на основе своего метода. Он послал Мерсенну пару решений, которые тот включил во вторую часть своей "Гармонии", опубликованной в 1637 году. Например, он предлагал общий метод нахождения дружественных чисел, подобный по структуре способу, который применял Евклид для нахождения совершенных чисел. Так, если три числа А = 3² · 2^2n‑1, В = 3 · 2^n‑1 и С = 3 х 2^n‑1 ‑ 1 простые, то 2ⁿА и 2ⁿВС дружественные. Обратите внимание на сходство данного результата с результатом Евклида о совершенных числах. Второй результат содержал подобную формулу для особого случая мультисовершенных чисел, которые являются третьей частью от суммы их собственных делителей. Рассуждение было аналогичным: если число некоего вида простое, то результат формулы – это число, дающее при умножении на 3 сумму собственных делителей. Ферма утверждал, что нашел подобные формулы для других мультисовершенных чисел, но они так и не стали известны.

У всех этих задач есть одна общая предпосылка: в каждой из них, прежде чем утверждать, можно считать число совершенным или пару чисел дружественными, или какое‑то из них – мультисовершенным, нужно понять, являются ли некоторые числа определенной структуры простыми. Следовательно, нет ничего странного в том, что в переписке с Мерсенном в конце 1630‑х годов Ферма все больше интересовало, существует ли способ установить, является ли число некоего вида простым.

МАЛАЯ ТЕОРЕМА ФЕРМА

Ферма понял, что основная задача теории чисел заключается в изучении простых чисел, проблемы разложения на простые множители и проблемы простоты числа (то есть определения, является ли число простым). Такое понимание делает его отцом современной теории чисел.

В античности Диофант опубликовал свою знаменитую "Арифметику", от которой сохранилась приблизительно половина. Это не трактат, как "Начала" Евклида, а сборник более чем 100 задач на определенные (с одним или небольшим количеством уникальных решений) и неопределенные уравнения (с бесконечным числом решений). В изложении его задач нет системного подхода, их решение обычно дается целенаправленно, индивидуально для каждой проблемы. Метод решения излагается в каждом отдельном случае в качестве примера. Когда Диофант сталкивался с неопределенным уравнением, он довольствовался тем, что находил только одно решение, игнорируя существование других возможных.

Поскольку греки считали, что числа бывают только рациональными положительными, числа же вроде √2 были странными "чудовищами", которые появлялись лишь в геометрии, то Диофант давал решения только для признаваемых греками чисел. Итак, игнорирование возможных решений, связанных с нерациональными числами, было характерным для Диофанта и все еще было живо в XVII веке. Рациональные числа в целом неразложимы на простые множители. Греки знали это, но хотя они были знакомы с простыми числами, они не создали дисциплину, посвященную исключительно числам, которые действительно разложимы на простые множители, то есть натуральным числам. Такую дисциплину основал Ферма, и он был первым, кто понял, что натуральные числа заслуживают отдельного изучения, и первым, кто заложил основы этого изучения анализом свойств простых чисел.

Простые числа – это кирпичи, из которых строятся все натуральные. Уже было рассмотрено несколько примеров, в которых важно, чтобы некая величина была простым числом. Но есть много других результатов, в которых все основывается на простых числах, поскольку исследование свойств этих кирпичиков позволяет делать утверждения, которые нельзя было бы сделать о натуральном числе в целом. У простых чисел есть интересные свойства, которыми не обладают составные (не простые) числа; следовательно, рассуждать о них и выводить свойства составных чисел на их основе – обычная стратегия в теории чисел.

Работы Ферма привлекли внимание математика по имени Бернар Френикль де Бесси (1605‑1675), члена кружка Мерсенна. Френикль хотя и не обладал математическим гением Ферма, сделал впечатляющую догадку о свойствах очень больших чисел. Он, как и другие ученые, вел переписку с Ферма: она началась в 1640 году, длилась с перерывами и закончилась почти через 20 лет. Эти отношения, что вообще характерно для Ферма, были сложными. Однако Френикль, возможно, был человеком, который лучше всего понимал вклад этого ученого в теорию чисел.