Теорема Евклида является фундаментальным элементом теории чисел. Она утверждает, что для любого конечного списка простых чисел найдётся простое число, не вошедшее в этот список (то есть существует бесконечно много простых чисел).
Имеется несколько известных доказательств этой теоремы.
Доказательство Евклида
Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (Книга IX, Предложение 20). При этом Евклид не использует понятие бесконечности, а доказывает это утверждение в следующей формулировке: простых чисел больше, чем любое выбранное конечное их множество.
Евклид доказывает это следующим образом.
Предположим, что дан некоторый конечный список простых чисел a , b , … z {displaystyle a,b,dots z} . Евклид доказывает, что существует простое число , не входящее в этот список.
Пусть P {displaystyle P} — наименьшее общее кратное этих чисел, P = a ∗ b ∗ . . . ∗ z {displaystyle P=a*b*...*z} .
Евклид рассматривает число Q = P + 1 {displaystyle Q=P+1} . Если Q {displaystyle Q} — простое, то найдено простое число, не входящее в данный список a , b , . . . . z {displaystyle {a,b,....z}} (поскольку оно больше каждого числа из списка).
Если же Q {displaystyle Q} не является простым, то существует некоторое простое число x {displaystyle x} , на которое нацело делится число Q {displaystyle Q} . Но x {displaystyle x} не может быть одновременно и делителем Q {displaystyle Q} , и элементом списка a , b , . . . . z {displaystyle {a,b,....z}} , поскольку тогда при делении Q {displaystyle Q} на x {displaystyle x} был бы остаток, равный единице. Значит, существует простое число x {displaystyle x} , не входящее ни в какой (конечный) список простых чисел a , b , . . . . z {displaystyle {a,b,....z}} .
Часто при изложении доказательства теоремы Евклида начинают с рассмотрения сразу множества ВСЕХ простых чисел (в предположении, что это множество содержит конечное число элементов), и далее ведут доказательство теоремы от противного. Хотя такое доказательство тоже возможно, оригинальное рассуждение Евклид проводит более элегантно - именно для любого конечного набора простых чисел, и доказывает, что должно существовать какое-то простое число, не входящее в этот (любой) набор простых чисел.
Краткая форма доказательства Евклида:
Некоторые связанные доказательства этой теоремы используют так называемые евклидовы числа (последовательность A006862 в OEIS): E n = p n # + 1 {displaystyle E_{n}=p_{n}#+1} , где p n # {displaystyle p_{n}#} — произведение первых n {displaystyle n} простых чисел (праймориал). При этом формально говоря доказательство, приведенное Евклидом, не использует эти числа. Как было сказано выше, Евклид показывает, что для любого конечного набора простых чисел (не обязательно первых n {displaystyle n} простых чисел) существует простое число, не включенное в этот набор.
Другие вариации доказательства Евклида используют факториал: n! делится на любое целое от 2 до n, так как он является их произведением. Следовательно, n! + 1 не делится ни на одно натуральное число от 2 до n включительно (при делении на любое из этих чисел в остатке получим 1). Таким образом, n! + 1 либо само является простым, либо делится на простое число, большее n. В любом случае мы имеем для любого натурального числа n по меньшей мере одно простое число, большее n. Отсюда делаем вывод, что простых чисел бесконечно много.
Доказательство Эйлера
Другое доказательство, предложенное Леонардом Эйлером, опирается на основную теорему арифметики, утверждающую, что любое целое число имеет единственное разложение на простые множители. Если обозначить через P множество всех простых чисел, можно записать равенства:
∏ p ∈ P 1 1 − 1 / p = ∏ p ∈ P ∑ k ⩾ 0 1 p k = ∑ n 1 n . {displaystyle prod _{pin P}{frac {1}{1-1/p}}=prod _{pin P}sum _{kgeqslant 0}{frac {1}{p^{k}}}=sum _{n}{frac {1}{n}}.}Первое равенство получается из формулы для геометрического ряда в каждом множителе произведения. Второе равенство получается перестановкой местами произведения и суммы:
∏ p ∈ P ∑ k ⩾ 0 1 p k = ∑ k ⩾ 0 1 2 k ⋅ ∑ k ⩾ 0 1 3 k ⋅ ∑ k ⩾ 0 1 5 k ⋅ ∑ k ⩾ 0 1 7 k ⋯ = ∑ k , ℓ , m , n , ⋯ ⩾ 0 1 2 k 3 ℓ 5 m 7 n ⋯ = ∑ n 1 n {displaystyle {egin{aligned}prod _{pin P}sum _{kgeqslant 0}{frac {1}{p^{k}}}&=sum _{kgeqslant 0}{frac {1}{2^{k}}}cdot sum _{kgeqslant 0}{frac {1}{3^{k}}}cdot sum _{kgeqslant 0}{frac {1}{5^{k}}}cdot sum _{kgeqslant 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}}}В результате любое произведение простых чисел появляется в формуле лишь один раз, а тогда, согласно основной теореме арифметики, сумма равна сумме по всем натуральным числам.
Сумма справа является гармоническим рядом, который расходится, так что произведение слева должно также расходиться, что невозможно, если число элементов в множестве P конечно.
При помощи этого доказательства Эйлером получено более сильное утверждение, чем теорема Евклида, а именно расходимость суммы обратных значений простых чисел.
Доказательство Эрдёша
Пал Эрдёш дал третье доказательство, которое также опирается на основную теорему арифметики. Сначала обратим внимание на то, что любое натуральное число n можно представить в виде
r s 2 {displaystyle rs^{2}} ,где r является свободным от квадратов (не делится на какой-либо полный квадрат). Мы можем взять в качестве s2 наибольший квадрат, делящий n, а тогда r = n/s2. Теперь предположим, что есть только конечное количество простых чисел и обозначим это количество простых чисел буквой k. Так как каждое простое число может появиться в разложении любого свободного от квадратов чисел только раз, согласно основной теореме арифметики, есть только 2k свободных от квадратов чисел.
Теперь фиксируем некоторое натуральное число N и рассмотрим натуральные числа между 1 и N. Каждое из этих чисел можно записать в виде rs2, где r — свободное от квадратов число, а s2 является квадратом:
( 1·1, 2·1, 3·1, 1·4, 5·1, 6·1, 7·1, 2·4, 1·9, 10·1, ...)В списке N различных чисел и каждое из них получается умножением свободного от квадратов числа на квадрат, не превосходящий N. Имеется ⌊ N ⌋ {displaystyle lfloor {sqrt {N}} floor } таких квадратов. Теперь образуем все возможные произведения всех квадратов, не превосходящих N, на все свободные от квадратов числа. Имеется в точности 2 k ⌊ N ⌋ {displaystyle 2^{k}lfloor {sqrt {N}} floor } таких чисел, все они различны и включают все числа из нашего списка, а может быть, и больше. Таким образом, 2 k ⌊ N ⌋ ⩾ N {displaystyle 2^{k}lfloor {sqrt {N}} floor geqslant N} . Здесь ⌊ x ⌋ {displaystyle lfloor {x} floor } означает целую часть.
Поскольку неравенство не выполняется для достаточно большого N, простых чисел должно быть бесконечно много.
Доказательство Фюрстенберга
В 1950-х годах Гилель Фюрстенберг предложил доказательство, использующее топологию точечных множеств.
Некоторые свежие доказательства
Пинаско
Хуан Пабло Пиаско предложил следующее доказательство.
Пусть p 1 , … ; p N {displaystyle p_{1},dots ;p_{N}} — наименьшие N простых чисел. Тогда согласно принципу включений-исключений, количество положительных целых чисел, не превосходящих x и делящихся на эти простые числа, равно
1 + ∑ i ⌊ x p i ⌋ − ∑ i < j ⌊ x p i p j ⌋ + ∑ i < j < k ⌊ x p i p j p k ⌋ − ⋯ ⋯ ± ( − 1 ) N + 1 ⌊ x p 1 ⋯ p N ⌋ . ( 1 ) {displaystyle {egin{aligned}1+sum _{i}leftlfloor {frac {x}{p_{i}}} ight floor -sum _{i<j}leftlfloor {frac {x}{p_{i}p_{j}}} ight floor &+sum _{i<j<k}leftlfloor {frac {x}{p_{i}p_{j}p_{k}}} ight floor -cdots &cdots pm (-1)^{N+1}leftlfloor {frac {x}{p_{1}cdots p_{N}}} ight floor .qquad (1)end{aligned}}}Разделив на x и устремив x → ∞ {displaystyle x o infty } , получим
∑ i 1 p i − ∑ i < j 1 p i p j + ∑ i < j < k 1 p i p j p k − ⋯ ± ( − 1 ) N + 1 1 p 1 ⋯ p N . ( 2 ) {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)}Это можно переписать как
1 − ∏ i = 1 N ( 1 − 1 p i ) . ( 3 ) {displaystyle 1-prod _{i=1}^{N}left(1-{frac {1}{p_{i}}} ight).qquad (3)}Если никаких других простых чисел, отличных от p 1 , … , p N {displaystyle p_{1},dots ,p_{N}} , не существует, выражение в (1) равно ⌊ x ⌋ {displaystyle lfloor x floor } и выражение (2) равно 1, однако ясно, что выражение (3) единице не равно. Таким образом, должны быть простые числа, отличные от p 1 , … , p N {displaystyle p_{1},dots ,p_{N}} .
Ванг
В 2010 году Джун Хо Питер Ванг опубликовал следующее доказательство от противного. Пусть k — некоторое натуральное число. Тогда, согласно формуле Лежандра
k ! = ∏ p prime p f ( p , k ) {displaystyle k!=prod _{p{ ext{ prime}}}p^{f(p,k)}} (произведение по всем простым числам)где
f ( p , k ) = ⌊ k p ⌋ + ⌊ k p 2 ⌋ + ⋯ . {displaystyle f(p,k)=leftlfloor {frac {k}{p}} ight floor +leftlfloor {frac {k}{p^{2}}} ight floor +cdots .} f ( p , k ) < k p + k p 2 + ⋯ = k p − 1 ⩽ k . {displaystyle f(p,k)<{frac {k}{p}}+{frac {k}{p^{2}}}+cdots ={frac {k}{p-1}}leqslant k.}Но если существует только конечное число простых чисел,
lim k → ∞ ( ∏ p p ) k k ! = 0 , {displaystyle lim _{k o infty }{frac {left(prod _{p}p ight)^{k}}{k!}}=0,}(числитель дроби растёт экспоненциально, в то время как по формуле Стирлинга знаменатель растёт быстрее простой экспоненциальности), что противоречит тому, что для каждого k числитель больше либо равен знаменателю.
Сайдак
Филлип Сайдак дал следующее конструктивное доказательство, которое не использует доведение до абсурда или лемму Евклида (о том, что, если простое число 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}, · · ·
даёт последовательность неограниченно расширяющихся множеств простых чисел.
Доказательство, использующее иррациональность π {displaystyle pi }
Представление формулы Лейбница для π {displaystyle pi } в виде произведения Эйлера даёт.
π 4 = 3 4 ⋅ 5 4 ⋅ 7 8 ⋅ 11 12 ⋅ 13 12 ⋅ 17 16 ⋅ 19 20 ⋅ 23 24 ⋅ 29 28 ⋅ 31 32 ⋅ ⋯ {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 } .
Доказательство, использующее теорию информации
Александр Шень и др. дали доказательство, использующее метод несжимаемости и колмогоровскую сложность:
Предположим, что имеется только k простых чисел ( p 1 , … , p k {displaystyle p_{1},dots ,p_{k}} ). Согласно основной теореме арифметики, любое натуральное число n представимо в виде
n = p 1 e 1 p 2 e 2 ⋯ p k e k , {displaystyle n={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}cdots {p_{k}}^{e_{k}},}где неотрицательные целые числа ei вместе со списком конечного размера простых чисел достаточны для реконструкции числа. Поскольку p i ⩾ 2 {displaystyle p_{i}geqslant 2} для всех i, отсюда следует, что все e i ⩽ log n {displaystyle e_{i}leqslant log n} (где log {displaystyle log } означает логарифм по основанию 2).
Это даёт метод кодирования для n следующего размера (используя нотацию «O большое»):
O ( prime list size + k log log n ) = O ( log log n ) {displaystyle O({ ext{prime list size}}+klog log n)=O(log log n)} бит.Это куда более эффективное кодирование, чем представление n непосредственно в двоичном коде, которое требует N = O ( log n ) {displaystyle N=O(log n)} бит. Установленный результат о сжатии без потерь утверждает, что нет алгоритма сжатия без потерь N бит информации в менее чем N бит. Вышеприведённое представление нарушает это утверждение, поскольку при достаточно больших n log log n = o ( log n ) {displaystyle log log n=o(log n)} .
Таким образом, простых чисел бесконечно много.
Асимптотика распределения простых чисел
Теорема о распределении простых чисел утверждает, что количество простых чисел меньших n, обозначаемое π ( n ) {displaystyle pi (n)} , растёт как n / ln ( n ) {displaystyle n/ln(n)} .