Просмотр кода страницы Теорема Евклида

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

==Доказательство Евклида==
Самое старое известное доказательство этого факта было дано [[Евклид]]ом в «[[Начала Евклида|Началах]]» (книга IX, утверждение 20<ref>James Williamson (translator and commentator), ''The Elements of Euclid, With Dissertations'', [[Clarendon Press]], Oxford, 1782, page 63, [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html English translation of Euclid’s proof]{{ref-en}}</ref>){{efn|Точная формулировка  утверждения Евклида: «Простых чисел больше, чем любое  предполагаемое число простых чисел». В доказательстве, из предположения, что существует по меньшей три простых числа, Евклид выводит существование четвёртого.}}.

Предположим, что имеется некоторый конечный список простых чисел <math>p_1, p_2, \dots, p_n</math>. Будет показано, что существует по меньшей мере ещё одно простое число, отсутствующее в списке. Пусть <math>P</math> — произведение всех простых чисел из списка: <math>P = p_1p_2{\dots}p_n</math>. Пусть <math>q = P + 1</math>. Тогда <math>q</math> либо является простым числом, либо нет:

*Если <math>q</math> является простым, то получили простое число, не входящее в список.
*Если <math>q</math> не является простым, то существует некоторое [[простое число]] <math>p</math>, которое является делителем числа <math>q</math>, так как каждое отличное от единицы натуральное число имеет делитель — простое число. Если это простое число в списке, то оно должно делить <math>P</math> (поскольку <math>P</math> является произведением всех чисел из списка). Но <math>p</math> делит <math>P + 1 = q</math>. Если <math>p</math> делит и <math>P</math>, и <math>q</math>, то оно будет делить разность {{efn|В общем случае для любых целых чисел <math>a</math>, <math>b</math> и <math>c</math>, если <math>a \mid b</math> и <math>a \mid c</math>, то <math> a \mid (b - c)</math>. Далее ''см.'' «[[Признаки делимости|Делимость]]».}} двух чисел, которая равна <math>(P + 1) - P</math> т.е. <math>1</math>. Поскольку ни одно простое число не делит <math>1</math>, <math>p</math> не может находиться в списке. Это означает, что существует по меньшей мере одно простое число, отсутствующее в списке.

Это доказывает, что для любого списка простых чисел существует простое число, не принадлежащее списку, а потому должно существовать бесконечно много простых чисел<ref>{{Статья|автор=Harry Furstenberg|заглавие=On the Infinitude of Primes|ссылка=http://www.jstor.org/stable/2307043|издание=The American Mathematical Monthly|год=1955|том=62|выпуск=5|страницы=353—353|doi=10.2307/2307043}}</ref>.

Часто сообщается, что Евклид начинает с предположения, что первоначально рассмотренное множество содержит все простые числа, и далее ведет доказательство теоремы от противного. Хотя такое доказательство верно, оригинальное рассуждение Евклида производится именно для произвольного конечного набора простых чисел.<ref>{{статья |заглавие=Prime Simplicity |издание=[[The Mathematical Intelligencer]] |том=31 |номер=4 |страницы=44—52 |doi=10.1007/s00283-009-9064-8 |язык=en |автор=Hardy, Michael; Woodgold, Catherine |год=2009 }}{{ref-en}}</ref>

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

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

Некоторые связанные доказательства этой теоремы используют так называемые {{iw|Евклидово число|евклидовы числа||Euclid number}} ({{OEIS|A006862}}): <math>E_n=p_n\#+1</math>, где <math>p_n\#</math> — произведение первых <math>n</math> простых чисел ([[праймориал]]). При этом формально говоря доказательство, приведенное Евклидом, не использует эти числа: Евклид показывает, что для ''любого'' конечного набора простых чисел (не обязательно первых <math>n</math> простых чисел) существует простое число, не включенное в этот набор<ref>{{Статья|автор=Romeo Mestrovic|заглавие=Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 B.C.--2012) and another new proof|ссылка=http://arxiv.org/abs/1202.3670|издание=arXiv:1202.3670 [math]|год=2012-02-16}}</ref>.

Другие вариации доказательства Евклида используют [[факториал]]: ''n''<nowiki>!</nowiki> делится на любое целое от 2 до ''n'', так как он является их произведением. Следовательно, {{nowrap|''n''! + 1}} не делится ни на одно натуральное число от 2 до ''n'' включительно (при делении на любое из этих чисел в остатке получим 1). Таким образом, {{nowrap|''n''! + 1}} либо само является простым, либо делится на простое число, большее ''n''. В любом случае мы имеем для любого натурального числа ''n'' по меньшей мере одно простое число, большее ''n''. Отсюда делаем вывод, что простых чисел бесконечно много{{sfn|Bostock, Chandler, Rourke|2014|с=168}}.

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

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

: <math>\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}.</math>

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

: <math>
\begin{align}
\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{align}
</math>

В результате любое произведение простых чисел появляется в формуле лишь один раз, а тогда, согласно основной теореме арифметики, сумма равна сумме по всем натуральным числам{{efn|Это равенство является специальным случаем формулы для {{не переведено 5|Произведение Эйлера|произведения Эйлера||Euler product}}  {{не переведено 5|Доказательство формулы произведения Эйлера для дзета-функции Римана|для дзета-функции Римана||Proof of the Euler product formula for the Riemann zeta function}}.}}.

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

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

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

[[Эрдёш, Пал|Пал Эрдёш]] дал третье доказательство, которое также опирается на основную теорему арифметики. Сначала обратим внимание на то, что любое натуральное число ''n'' можно представить в виде 
: <math>rs^2</math>,

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

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

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

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

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

==Доказательство Фюрстенберга==
{{Основная статья|Доказательстово Фюрстенберга бесконечности числа простых чисел}}
В 1950-х годах {{не переведено 5|Фюрстенберг, Гилель|Гилель Фюрстенберг||Hillel Furstenberg}} предложил доказательство, использующее {{не переведено 5|Топология точечных множеств|топологию точечных множеств||point-set topology}}.

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

===Пинаско===

Хуан Пабло Пиаско предложил следующее доказательство{{sfn|Pinasco|2009|с=172–173}}.

Пусть <math>p_1,\dots;p_N</math> — наименьшие ''N'' простых чисел. Тогда согласно принципу [[Формула включений-исключений|принципу включений-исключений]], количество положительных целых чисел, не превосходящих ''x'' и делящихся на эти простые числа, равно

: <math>
\begin{align}
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{align}
</math>

Разделив на ''x'' и устремив <math>x \to \infty</math>, получим

: <math> \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) </math>

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

: <math> 1 - \prod_{i=1}^N \left( 1 - \frac{1}{p_i} \right). \qquad (3) </math>

Если никаких других простых чисел, отличных от <math>p_1,\dots,p_N</math>, не существует, выражение в (1) равно <math>\lfloor x \rfloor </math> и выражение (2) равно 1, однако ясно, что выражение (3) единице не равно. Таким образом, должны быть простые числа, отличные от <math>p_1,\dots,p_N</math>.

===Ванг===

В 2010 году Джун Хо Питер Ванг опубликовал следующее доказательство от противного{{sfn|Whang|2010|с=181}}.  Пусть ''k'' — некоторое натуральное число.  Тогда, согласно {{не переведено 5|Формула Лежандра|формуле Лежандра||Legendre's formula}}

: <math> k! = \prod_{p\text{ prime}} p^{f(p,k)} </math> (произведение по всем простым числам)

где

: <math> f(p,k) = \left\lfloor \frac{k}{p} \right\rfloor + \left\lfloor \frac{k}{p^2} \right\rfloor + \cdots. </math>

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

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

: <math> \lim_{k\to\infty} \frac{\left(\prod_p p\right)^k}{k!} = 0, </math>

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

===Сайдак===

Филлип Сайдак дал следующее [[конструктивное доказательство]], которое не использует [[доведение до абсурда]]{{sfn|Saidak|2006|}} или лемму Евклида (о том, что, если простое число ''p'' делит ''ab'', оно должно делить либо ''a'', либо ''b'').

Поскольку каждое натуральное число (>&nbsp;1) имеет по меньшей мере один простой множитель, а два последовательных числа ''n'' и (''n''&nbsp;+&nbsp;1) не имеют общего делителя, произведение ''n''(''n''&nbsp;+&nbsp;1) имеет больше различных простых делителей, чем само число ''n''. Таким образом, цепочка [[Прямоугольное число|прямоугольных чисел]]:<br>1·2 = 2 {2}, &nbsp; &nbsp;2·3 = 6 {2, 3}, &nbsp; &nbsp;6·7 = 42 {2,3, 7}, &nbsp; &nbsp;42·43 = 1806 {2,3,7, 43}, &nbsp; &nbsp;1806·1807 = 3263443 {2,3,7,43, 13,139}, · · ·<br>даёт последовательность неограниченно расширяющихся множеств простых чисел.

== Доказательство, использующее иррациональность <math>\pi</math>==
Представление [[Ряд Лейбница|формулы Лейбница для <math>\pi</math>]] в виде {{не переведено 5|Произведение Эйлера|произведения Эйлера||Euler product}} даёт{{sfn|Debnath|2010|с=214}}.
:<math> \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 </math>
Числителями являются нечётные простые числа, а каждый знаменатель является ближайшим к числителю числом, кратным 4.

Если бы простых чисел было конечное количество, эта формула дала бы для <math>\pi</math> рациональное представление, знаменатель которого является произведением всех чисел, что противоречит [[Иррациональное число|иррациональности]] <math>\pi</math>.

==Доказательство, использующее теорию информации ==
[[Александр Шень]] и др. дали доказательство, использующее {{не переведено 5|метод несжимаемости|||Incompressibility method}}{{sfn|Верещагин, Успенский, Шень|2013|с=267}} и [[Колмогоровская сложность|колмогоровскую сложность]]:

Предположим, что имеется только ''k'' простых чисел (<math>p_1,\dots,p_k</math>). Согласно [[Основная теорема арифметики|основной теореме арифметики]], любое натуральное число ''n'' представимо в виде

:<math>n = {p_1}^{e_1} {p_2}^{e_2} \cdots {p_k}^{e_k},</math>

где неотрицательные целые числа ''e''<sub>i</sub> вместе со списком конечного размера простых чисел достаточны для реконструкции числа. Поскольку <math>p_i \geqslant 2</math> для всех ''i'', отсюда следует, что все <math>e_i \leqslant \log n</math> (где <math>\log</math> означает логарифм по основанию 2).

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

:<math>O(\text{prime list size} + k \log \log n) = O(\log \log n)</math> бит.

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

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

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

[[Теорема о распределении простых чисел]] утверждает, что количество простых чисел меньших ''n'', обозначаемое <math>\pi(n)</math>, растёт как <math>n/\ln(n)</math>.<ref>{{Статья|автор=Диамонд Г.|заглавие=Элементарные методы в изучении распределения простых чисел|ссылка=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=4716&option_lang=rus|язык=|издание=[[УМН]]|год=1990|месяц=|число=|том=|номер=|страницы=|issn=}}</ref>


==См. также==
* [[Теорема Дирихле о простых числах в арифметической прогрессии]]
* [[Теорема о распределении простых чисел]]

== Комментарии ==
{{Комментарии}}

==Примечания==
{{примечания|2}}
==Литература==
{{refbegin|colwidth=30em}}
* {{статья
|автор=Michael Hardy, Catherine Woodgold
|ref=Hardy, Woodgold
|заглавие=Prime Simplicity
|издание=[[The Mathematical Intelligencer]]
|том=31
|номер=4
|год=2009
|страницы=44—52.
|язык=en
}}
* {{статья
|ответственный=James Williamson (перевод и комментарии)
|ref=Williamson
|заглавие=The Elements of Euclid, With Dissertations
|издание=[[Clarendon Press]]
|издательство=Oxford
|год=1782
|страницы=63
}}
*{{книга
|заглавие=Further Pure Mathematics
|ref=Bostock, Chandler, Rourke|
|автор=Linda| Bostock, Suzanne Chandler, C. Rourke|
|год=2014
|месяц=11
|издательство=Nelson Thornes
|isbn=9780859501033
|страницы=168
}}
*{{статья
|автор=Junho Peter Whang
|ref=Whang
|заглавие=Another Proof of the Infinitude of the Prime Numbers
|издание=[[American Mathematical Monthly]]
|том=117
|номер=2
|месяц=February
|год=2010
|страницы=181
}}
*{{статья
|заглавие=A New Proof of Euclid's Theorem
|ссылка=http://fermatslibrary.com/s/a-new-proof-of-euclids-theorem
|автор=Filip Saidak
|ref=Saidak
|месяц=December
|год=2006
|издание=[[American Mathematical Monthly]]
|том=113
|выпуск=10
|doi=10.2307/27642094
}}
*{{статья
|заглавие=The Legacy of Leonhard Euler: A Tricentennial Tribute|
|автор=Lokenath Debnath
|ref=Debnath
|издательство=World Scientific
|год=2010
|isbn=9781848165267
|страницы=214
|ссылка=https://books.google.com/books?id=K2liU-SHl6EC&pg=PA214
}}
*{{статья
|заглавие=Колмогоровская сложность и алгоритмическая случайность
|автор=[[Николай Константинович Верещагин]], [[Владимир Андреевич Успенский]], [[Александр Шень]]
|ref=Верещагин, Успенский, Шень
|издательство=Издательство Московского центра непрерывного математического образования
|год=2013
|ссылка=http://www.lirmm.fr/~ashen/kolmbook.pdf
}}
*{{статья
|автор=Juan Pablo Pinasco
|ref=Pinasco
|заглавие=New Proofs of Euclid's and Euler's theorems
|издание=[[American Mathematical Monthly]]
|том=116
|номер=2
|месяц=February
|год=2009
}}
{{refend}}

==Ссылки==
* {{MathWorld|urlname=EuclidsTheorems|title=Euclid's Theorem}}
* [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html Euclid's Elements, Book IX, Prop. 20] (Euclid's proof, on David Joyce's website at Clark University)
* [https://arxiv.org/abs/1202.3670 125 proofs of Euclid's theorem]
[[Категория:Теоремы о простых числах]]
[[Категория:Основные теоремы]]
{{rq|checktranslate|style}}