Теорема Евклида

Теорема Евклида — основной элемент теории чисел. Она утверждает, что для любого конечного списка простых чисел найдётся простое число, не вошедшее в этот список (то есть существует бесконечно много простых чисел).

Имеется несколько известных доказательств этой теоремы.

Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (Книга IX, Предложение 20^[1]). При этом Евклид не использует понятие бесконечности, а доказывает это утверждение в следующей формулировке: простых чисел больше, чем любое выбранное конечное их множество.

Евклид доказывает это следующим образом^[2].

Предположим, что дан некоторый конечный список простых чисел ${\displaystyle a,b,\dots z}$. Евклид доказывает, что существует простое число, не входящее в этот список.

Пусть ${\displaystyle P}$ — наименьшее общее кратное этих чисел, ${\displaystyle P=a*b*...*z}$.

Евклид рассматривает число ${\displaystyle Q=P+1}$. Если ${\displaystyle Q}$ — простое, то найдено простое число, не входящее в данный список ${\displaystyle {a,b,....z}}$ (поскольку оно больше каждого числа из списка).

Если же ${\displaystyle Q}$ не является простым, то существует некоторое простое число ${\displaystyle x}$, на которое нацело делится число ${\displaystyle Q}$. Но ${\displaystyle x}$ не может быть одновременно и делителем ${\displaystyle Q}$, и элементом списка ${\displaystyle {a,b,....z}}$ , поскольку тогда при делении ${\displaystyle Q}$ на ${\displaystyle x}$ был бы остаток, не равный нулю. Значит, существует простое число ${\displaystyle x}$, не входящее ни в какой (конечный) список простых чисел ${\displaystyle {a,b,....z}}$.

Часто при изложении доказательства теоремы Евклида начинают с рассмотрения сразу множества всех простых чисел (в предположении, что это множество содержит конечное число элементов), и далее ведут доказательство теоремы от противного. Хотя такое доказательство тоже возможно, оригинальное рассуждение Евклид проводит более элегантно — именно для любого конечного набора простых чисел, и доказывает, что должно существовать какое-то простое число, не входящее в этот (любой) набор простых чисел^[3].

Краткая форма доказательства Евклида:

Другие вариации доказательства Евклида используют факториал: n! делится на любое целое от 2 до n, так как он является их произведением. Следовательно, n! + 1 не делится ни на одно натуральное число от 2 до n включительно (при делении на любое из этих чисел в остатке получим 1). Таким образом, n! + 1 либо само является простым, либо делится на простое число, большее n. В любом случае мы имеем для любого натурального числа n по меньшей мере одно простое число, большее n. Отсюда делаем вывод, что простых чисел бесконечно много^[4].

Некоторые связанные доказательства этой теоремы используют так называемые евклидовы числа (последовательность A006862 в OEIS): ${\displaystyle E_{n}=p_{n}\#+1}$, где ${\displaystyle p_{n}\#}$ — произведение первых ${\displaystyle n}$ простых чисел (праймориал). При этом, формально говоря, доказательство, приведенное Евклидом, не использует эти числа. Как было сказано выше, Евклид показывает, что для любого конечного набора простых чисел (не обязательно первых ${\displaystyle n}$ простых чисел) существует простое число, не включенное в этот набор^[5].

Другое доказательство, предложенное Леонардом Эйлером, опирается на основную теорему арифметики, утверждающую, что любое целое число имеет единственное разложение на простые множители. Если обозначить через P множество всех простых чисел, можно записать равенства:

${\displaystyle \prod _{p\in P}{\frac {1}{1-1/p}}=\prod _{p\in P}\sum _{k\geqslant 0}{\frac {1}{p^{k}}}=\sum _{n}{\frac {1}{n}}.}$

Первое равенство получается из формулы для геометрического ряда в каждом множителе произведения. Второе равенство получается перестановкой местами произведения и суммы:

${\displaystyle {\begin{aligned}\prod _{p\in P}\sum _{k\geqslant 0}{\frac {1}{p^{k}}}&=\sum _{k\geqslant 0}{\frac {1}{2^{k}}}\cdot \sum _{k\geqslant 0}{\frac {1}{3^{k}}}\cdot \sum _{k\geqslant 0}{\frac {1}{5^{k}}}\cdot \sum _{k\geqslant 0}{\frac {1}{7^{k}}}\cdots \\[8pt]&=\sum _{k,\ell ,m,n,\cdots \geqslant 0}{\frac {1}{2^{k}3^{\ell }5^{m}7^{n}\cdots }}=\sum _{n}{\frac {1}{n}}\end{aligned}}}$

В результате любое произведение простых чисел появляется в формуле лишь один раз, а тогда, согласно основной теореме арифметики, сумма равна сумме по всем натуральным числам^[a].

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

При помощи этого доказательства Эйлером получено более сильное утверждение, чем теорема Евклида, а именно расходимость суммы обратных значений простых чисел.

Пал Эрдёш дал третье доказательство, которое также опирается на основную теорему арифметики. Сначала обратим внимание на то, что любое натуральное число n можно представить в виде

${\displaystyle rs^{2}}$,

где r является свободным от квадратов (не делится на какой-либо полный квадрат). Мы можем взять в качестве s² наибольший квадрат, делящий n, а тогда r = n/s². Теперь предположим, что есть только конечное количество простых чисел и обозначим это количество простых чисел буквой k. Так как каждое простое число может появиться в разложении любого свободного от квадратов чисел только раз, согласно основной теореме арифметики, есть только 2^k свободных от квадратов чисел.

Теперь фиксируем некоторое натуральное число N и рассмотрим натуральные числа между 1 и N. Каждое из этих чисел можно записать в виде rs², где r — свободное от квадратов число, а s² является квадратом:

( 1·1, 2·1, 3·1, 1·4, 5·1, 6·1, 7·1, 2·4, 1·9, 10·1, ...)

В списке N различных чисел и каждое из них получается умножением свободного от квадратов числа на квадрат, не превосходящий N. Имеется ${\displaystyle \lfloor {\sqrt {N}}\rfloor }$ таких квадратов. Теперь образуем все возможные произведения всех квадратов, не превосходящих N, на все свободные от квадратов числа. Имеется в точности ${\displaystyle 2^{k}\lfloor {\sqrt {N}}\rfloor }$ таких чисел, все они различны и включают все числа из нашего списка, а может быть, и больше. Таким образом, ${\displaystyle 2^{k}\lfloor {\sqrt {N}}\rfloor \geqslant N}$. Здесь ${\displaystyle \lfloor {x}\rfloor }$ означает целую часть.

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

В 1955 году Гилель Фюрстенберг опубликовал новое доказательство бесконечности числа простых чисел, используя топологию точечных множеств^[англ.].

В 2006 году Филлип Сайдак дал следующее конструктивное доказательство, которое не использует доведение до абсурда^[6] или лемму Евклида (о том, что, если простое число 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}, · · ·
даёт последовательность неограниченно расширяющихся множеств простых чисел.

В 2009 году Хуан Пабло Пиаско предложил следующее доказательство^[7].

Пусть ${\displaystyle p_{1},\dots ;p_{N}}$ — наименьшие N простых чисел. Тогда согласно принципу включений-исключений, количество положительных целых чисел, не превосходящих x и делящихся на эти простые числа, равно

${\displaystyle {\begin{aligned}1+\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor -\sum _{i<j}\left\lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor &+\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_{j}p_{k}}}\right\rfloor -\cdots \\&\cdots \pm (-1)^{N+1}\left\lfloor {\frac {x}{p_{1}\cdots p_{N}}}\right\rfloor .\qquad (1)\end{aligned}}}$

Разделив на x и устремив ${\displaystyle x\to \infty }$, получим

${\displaystyle \sum _{i}{\frac {1}{p_{i}}}-\sum _{i<j}{\frac {1}{p_{i}p_{j}}}+\sum _{i<j<k}{\frac {1}{p_{i}p_{j}p_{k}}}-\cdots \pm (-1)^{N+1}{\frac {1}{p_{1}\cdots p_{N}}}.\qquad (2)}$

Это можно переписать как

${\displaystyle 1-\prod _{i=1}^{N}\left(1-{\frac {1}{p_{i}}}\right).\qquad (3)}$

Если никаких других простых чисел, отличных от ${\displaystyle p_{1},\dots ,p_{N}}$, не существует, выражение в (1) равно ${\displaystyle \lfloor x\rfloor }$ и выражение (2) равно 1, однако ясно, что выражение (3) единице не равно. Таким образом, должны быть простые числа, отличные от ${\displaystyle p_{1},\dots ,p_{N}}$.

В 2010 году Джун Хо Питер Ванг опубликовал следующее доказательство от противного^[8]. Пусть k — некоторое натуральное число. Тогда, согласно формуле Лежандра^[англ.]

${\displaystyle k!=\prod _{p{\text{ prime}}}p^{f(p,k)}}$ (произведение по всем простым числам)

где

${\displaystyle f(p,k)=\left\lfloor {\frac {k}{p}}\right\rfloor +\left\lfloor {\frac {k}{p^{2}}}\right\rfloor +\cdots .}$

${\displaystyle f(p,k)<{\frac {k}{p}}+{\frac {k}{p^{2}}}+\cdots ={\frac {k}{p-1}}\leqslant k.}$

Но если существует только конечное число простых чисел,

${\displaystyle \lim _{k\to \infty }{\frac {\left(\prod _{p}p\right)^{k}}{k!}}=0,}$

(числитель дроби растёт экспоненциально, в то время как по формуле Стирлинга знаменатель растёт быстрее простой экспоненциальности), что противоречит тому, что для каждого k числитель больше либо равен знаменателю.

Представление формулы Лейбница для ${\displaystyle \pi }$ в виде произведения Эйлера^[англ.] даёт^[9].

${\displaystyle {\frac {\pi }{4}}={\frac {3}{4}}\cdot {\frac {5}{4}}\cdot {\frac {7}{8}}\cdot {\frac {11}{12}}\cdot {\frac {13}{12}}\cdot {\frac {17}{16}}\cdot {\frac {19}{20}}\cdot {\frac {23}{24}}\cdot {\frac {29}{28}}\cdot {\frac {31}{32}}\cdot \cdots }$

Числителями являются нечётные простые числа, а каждый знаменатель является ближайшим к числителю числом, кратным 4.

Если бы простых чисел было конечное количество, эта формула дала бы для ${\displaystyle \pi }$ рациональное представление, знаменатель которого является произведением всех чисел, что противоречит иррациональности ${\displaystyle \pi }$.

Александр Шень и др. дали доказательство, использующее метод несжимаемости^{[англ.][10]} и колмогоровскую сложность:

Предположим, что имеется только k простых чисел (${\displaystyle p_{1},\dots ,p_{k}}$). Согласно основной теореме арифметики, любое натуральное число n представимо в виде

${\displaystyle n={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\cdots {p_{k}}^{e_{k}},}$

где неотрицательные целые числа e_i вместе со списком конечного размера простых чисел достаточны для реконструкции числа. Поскольку ${\displaystyle p_{i}\geqslant 2}$ для всех i, отсюда следует, что все ${\displaystyle e_{i}\leqslant \log n}$ (где ${\displaystyle \log }$ означает логарифм по основанию 2).

Это даёт метод кодирования для n следующего размера (используя нотацию «O большое»):

${\displaystyle O({\text{prime list size}}+k\log \log n)=O(\log \log n)}$ бит.

Это куда более эффективное кодирование, чем представление n непосредственно в двоичном коде, которое требует ${\displaystyle N=O(\log n)}$ бит. Установленный результат о сжатии без потерь утверждает, что нет алгоритма сжатия без потерь N бит информации в менее чем N бит. Вышеприведённое представление нарушает это утверждение, поскольку при достаточно больших n ${\displaystyle \log \log n=o(\log n)}$.

Таким образом, простых чисел бесконечно много.

Теорема о распределении простых чисел утверждает, что количество простых чисел меньших n, обозначаемое ${\displaystyle \pi (n)}$, растёт как ${\displaystyle n/\ln(n)}$^[11].

• Теорема Дирихле о простых числах в арифметической прогрессии
• Теорема о распределении простых чисел

• Weisstein, Eric W. Euclid's Theorem (англ.) на сайте Wolfram MathWorld.
• Euclid's Elements, Book IX, Prop. 20 (Euclid's proof, on David Joyce's website at Clark University)
• 125 proofs of Euclid's theorem