WikiSort.ru - Не сортированное

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

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

Самое старое известное доказательство этого факта было дано Евклидом в «Началах» (книга IX, утверждение 20^[1])^{[lower-alpha 1]}.

Предположим, что имеется некоторый конечный список простых чисел ${\displaystyle p_{1},p_{2},\dots ,p_{n}}$ . Будет показано, что существует по меньшей мере ещё одно простое число, отсутствующее в списке. Пусть P — произведение всех простых чисел из списка: ${\displaystyle P=p_{1}p_{2}{\dots }p_{n}}$ . Пусть ${\displaystyle q=P+1}$ . Тогда q либо является простым числом, либо нет:

• Если q является простым, то получили простое число, не входящее в список.
• Если q не является простым, то некоторое простое число p делит q. Если это простое число в списке, то оно должно делить P (поскольку P является произведением всех чисел из списка). Но p делит ${\displaystyle P+1=q}$ . Если p делит и P, и q, то оно будет делить разность ^{[lower-alpha 2]} двух чисел, которая равна ${\displaystyle (P+1)-P}$ или просто 1. Поскольку ни одно простое число не делит 1, p не может находиться в списке. Это означает, что существует по меньшей мере одно простое число, отсутствующее в списке.

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

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

Доказательство Евклида может быть кратко воспроизведено так:

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

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

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

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

Сумма справа является гармоническим рядом, который расходится, так что произведение слева должно также расходиться, что невозможно, если число элементов в множестве 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, простых чисел должно быть бесконечно много.

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

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

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

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

Представление формулы Лейбница для ${\displaystyle \pi }$ в виде произведения Эйлера^[en] даёт^[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 }$ .

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

Александр Шень и др. дали доказательство, использующее метод несжимаемости^[en][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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.