Введение

Существует бесконечно много простых чисел.
Теорема о бесконечности простых чисел.

Теорема Евклида — фундаментальное утверждение в теории чисел, которое утверждает, что существует бесконечно много простых чисел. Она была впервые доказана Евклидом в его труде «Начала». Существует несколько доказательств этой теоремы.

Доказательство Евклида

Евклид предложил доказательство, опубликованное в его работе «Начала» (книга IX, предложение 20), которое перефразировано здесь. Рассмотрим любой конечный список простых чисел p1, p2, …, pn. Будет показано, что существует по крайней мере одно дополнительное простое число, не входящее в этот список. Пусть P будет произведением всех простых чисел в списке: P = p1p2…pn. Пусть q = P + 1. Тогда q либо простое, либо нет:

Если q простое, то существует по крайней мере еще одно простое число, не входящее в список, а именно, само q. Если q не является простым, то некоторый простой делитель p делит q. Если бы этот делитель p был в нашем списке, то он делил бы P (поскольку P является произведением всех чисел в списке); но p также делит P + 1 = q, как было сказано ранее. Если p делит P и q, то p также должно делить разность между этими двумя числами, которая равна (P + 1) − P, то есть 1. Поскольку никакое простое число не делит 1, p не может быть в списке. Это означает, что помимо чисел в списке существует по крайней мере еще одно простое число. Таким образом, доказано, что для каждого конечного списка простых чисел существует простое число, не входящее в этот список. В оригинальной работе, поскольку у Евклида не было способа записать произвольный список простых чисел, он использовал метод, который он часто применял, то есть метод обобщаемого примера. А именно, он выбирает только три простых числа и, используя общий метод, описанный выше, доказывает, что он всегда может найти дополнительное простое число. Евклид, вероятно, предполагал, что его читатели убеждены, что подобное доказательство будет работать, независимо от количества изначально выбранных простых чисел. Евклида часто ошибочно считают, что он доказал этот результат от противного, начиная с предположения, что конечное множество, изначально рассматриваемое, содержит все простые числа, хотя на самом деле это доказательство по случаям, прямой метод доказательства. Философ Торкель Францен в своей книге по логике утверждает: «Доказательство Евклида о том, что существует бесконечно много простых чисел, не является косвенным доказательством [ ]. Аргумент иногда формулируется как косвенное доказательство, заменяя его предположением: «Предположим, q1, …, qn – все простые числа». Однако, поскольку это предположение даже не используется в доказательстве, переформулировка бессмысленна».

Доказательство Эрдоса

Пол Эрдош привел доказательство, которое также опирается на основную теорему арифметики. Каждое положительное целое число имеет единственное разложение на квадратное свободное число r и полный квадрат s². Например, пусть N – положительное целое число, а k – количество простых чисел, меньших или равных N. Обозначим эти простые числа p₁, …, pk. Любое положительное целое число a, меньшее или равное N, тогда можно представить в виде

где каждый ei равен либо 0, либо 1. Существует 2ᵏ способов сформировать квадратное свободную часть числа a. А s² может быть не больше N, следовательно, не более N чисел можно представить в такой форме. Иными словами,

Или, перефразируя, k, количество простых чисел, меньших или равных N, больше или равно . Поскольку N было произвольным, k можно сделать сколь угодно большим, правильно выбирая N.

Доказательство построением

Филип Сайдак привел следующее доказательство построением, которое не использует доказательство от противного (reductio ad absurdum) или лемму Евклида (утверждающую, что если простое число p делит произведение ab, то оно должно делить либо a, либо b). Поскольку каждое натуральное число, большее 1, имеет хотя бы один простой делитель, а два последовательных числа n и (n + 1) не имеют общих делителей, произведение n(n + 1) имеет больше различных простых делителей, чем само число n. Таким образом, цепочка пронических чисел: 1 × 2 = 2 {2}, 2 × 3 = 6 {2, 3}, 6 × 7 = 42 {2, 3, 7}, 42 × 43 = 1806 {2, 3, 7, 43}, 1806 × 1807 = 3263442 {2, 3, 7, 43, 13, 139}, · · · предоставляет последовательность неограниченно возрастающих множеств простых чисел.

Более сильные результаты

Теоремы в этом разделе одновременно доказывают теорему Евклида и другие результаты.

Теорема Дирихле об арифметических прогрессиях

Теорема Дирихле утверждает, что для любых двух положительных взаимно простых целых чисел a и d существует бесконечно много простых чисел вида a + nd, где n — также положительное целое число. Иными словами, существует бесконечно много простых чисел, сравнимых с a по модулю d.