Теорема Евклида (Mykjybg Yftln;g)

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

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

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

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

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

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

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

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

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

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

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

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

Вариация доказательства Евклида с использованием факториала

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

Евклидовы числа

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

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

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

$\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}}.$

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

${\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}}$

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

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

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

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

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

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

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

Доказательство Фюрстенберга

Основная статья: Доказательстово Фюрстенберга

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

Новые доказательства

Сайдак

В 2006 году Филлип Сайдак дал следующее конструктивное доказательство, которое не использует доведение до абсурда или лемму Евклида (о том, что, если простое число 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 году Хуан Пабло Пиаско предложил следующее доказательство.

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

${\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 и устремив $x\to \infty$, получим

$\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-\prod _{i=1}^{N}\left(1-{\frac {1}{p_{i}}}\right).\qquad (3)$

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

Ванг

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

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

где

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

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

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

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

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

Доказательство, использующее иррациональность $\pi$

Представление формулы Лейбница для $\pi$ в виде произведения Эйлера даёт.

${\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.

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

Доказательство, использующее теорию информации

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

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

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

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

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

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

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

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

Асимптотика распределения простых чисел

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

См. также

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

Ссылки

• 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