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

Существует бесконечно много простых чисел.

Теорема Евклида — фундаментальное утверждение в теории чисел , утверждающее, что существует бесконечно много простых чисел. Впервые она была доказана Евклидом в его труде «Начала» . Существует несколько доказательств теоремы.

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

Евклид предложил доказательство, опубликованное в его труде «Начала» (книга IX, предложение 20) ^[1] , которое перефразировано здесь. ^[2]

Рассмотрим любой конечный список простых чисел p ₁ ,  p ₂ , ...,  p _n . Будет показано, что существует по крайней мере одно дополнительное простое число, не включенное в этот список. Пусть P будет произведением всех простых чисел в списке: P  =  p ₁ p ₂ ... p _n . Пусть q  =  P  + 1. Тогда q либо простое, либо нет:

• Если q — простое число, то существует по крайней мере еще одно простое число, которого нет в списке, а именно само q .
• Если q не является простым числом, то некоторый простой множитель p делит  q . Если бы этот множитель p был в нашем списке, то он делил бы P (так как P является произведением каждого числа в списке); но p также делит P  + 1 =  q , как только что было сказано. Если p делит P , а также q, то p также должно делить разность ^[3] двух чисел, которая равна ( P  + 1) −  P или просто 1. Поскольку ни одно простое число не делит 1, p не может быть в списке. Это означает, что существует по крайней мере еще одно простое число помимо тех, что в списке.

Это доказывает, что для каждого конечного списка простых чисел существует простое число, которого нет в списке. ^[4] В оригинальной работе, поскольку у Евклида не было возможности написать произвольный список простых чисел, он использовал метод, который он часто применял, то есть метод обобщаемого примера. А именно, он выбирает всего три простых числа и, используя общий метод, описанный выше, доказывает, что он всегда может найти дополнительное простое число. Евклид, по-видимому, предполагает, что его читатели убеждены, что подобное доказательство будет работать, независимо от того, сколько простых чисел было выбрано изначально. ^[5]

Евклид часто ошибочно утверждает, что доказал этот результат от противного, начав с предположения, что изначально рассматриваемое конечное множество содержит все простые числа, ^[6] хотя на самом деле это доказательство по случаям , метод прямого доказательства . Философ Торкель Францен в книге по логике утверждает: «Доказательство Евклида о том, что существует бесконечно много простых чисел, не является косвенным доказательством [...] Аргумент иногда формулируют как косвенное доказательство, заменяя его предположением «Предположим, что q ₁ , ... q _n — все простые числа». Однако, поскольку это предположение даже не используется в доказательстве, переформулировка бессмысленна». ^[7]

Вариации

Существует несколько вариантов доказательства Евклида, включая следующие:

Факториал n ! положительного целого числа n делится на каждое целое число от 2 до n , так как он является произведением всех этих чисел. Следовательно, n ! + 1 не делится ни на одно из целых чисел от 2 до n , включительно (оно дает остаток 1 при делении на каждое из них). Следовательно , n ! + 1 является либо простым числом, либо делится на простое число, большее  n . В любом случае для каждого положительного целого числа n существует по крайней мере одно простое число, большее  n . Вывод состоит в том, что количество простых чисел бесконечно. ^[8]

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

Другое доказательство, швейцарского математика Леонарда Эйлера , опирается на фундаментальную теорему арифметики : каждое целое число имеет уникальное разложение на простые множители. То, что написал Эйлер (не с этой современной нотацией и, в отличие от современных стандартов, не ограничивая аргументы в суммах и произведениях любыми конечными наборами целых чисел), эквивалентно утверждению, что мы имеем ^[9]

$${\displaystyle \prod _{p\in P_{k}}{\frac {1}{1-{\frac {1}{p}}}}=\sum _{n\in N_{k}}{\frac {1}{n}},}$$

где обозначает множество из k первых простых чисел, а — множество положительных целых чисел, все простые множители которых находятся в ${\displaystyle P_{k}}$ ${\displaystyle N_{k}}$ ${\displaystyle P_{k}.}$

Чтобы показать это, разложим каждый множитель в произведении в геометрический ряд и распределим произведение по сумме (это частный случай формулы произведения Эйлера для дзета-функции Римана ).

$${\displaystyle {\begin{aligned}\prod _{p\in P_{k}}{\frac {1}{1-{\frac {1}{p}}}}&=\prod _{p\in P_{k}}\sum _{i\geq 0}{\frac {1}{p^{i}}}\\&=\left(\sum _{i\geq 0}{\frac {1}{2^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{3^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{5^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{7^{i}}}\right)\cdots \\&=\sum _{\ell ,m,n,p,\ldots \geq 0}{\frac {1}{2^{\ell }3^{m}5^{n}7^{p}\cdots }}\\&=\sum _{n\in N_{k}}{\frac {1}{n}}.\end{aligned}}}$$

В предпоследней сумме каждое произведение простых чисел появляется ровно один раз, поэтому последнее равенство верно по основной теореме арифметики. В своем первом следствии к этому результату Эйлер обозначает символом, похожим на «абсолютную бесконечность», и пишет, что бесконечная сумма в утверждении равна «значению» , которому, таким образом, равно и бесконечное произведение (в современной терминологии это эквивалентно утверждению, что частичная сумма до гармонического ряда расходится асимптотически как ). Затем во втором следствии Эйлер отмечает, что произведение ${\displaystyle \infty }$ ${\displaystyle \log \infty }$ ${\displaystyle x}$ ${\displaystyle \log x}$

$${\displaystyle \prod _{n\geq 2}{\frac {1}{1-{\frac {1}{n^{2}}}}}}$$

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

Символ, используемый Эйлером для обозначения бесконечности

В той же статье (теорема 19) Эйлер фактически использовал приведенное выше равенство для доказательства гораздо более сильной теоремы, которая была неизвестна до него, а именно, что ряд

$${\displaystyle \sum _{p\in P}{\frac {1}{p}}}$$

является расходящимся , где P обозначает множество всех простых чисел (Эйлер пишет, что бесконечная сумма равна , что в современной терминологии эквивалентно утверждению, что частичная сумма до этого ряда ведет себя асимптотически как ). ${\displaystyle \log \log \infty }$ ${\displaystyle x}$ ${\displaystyle \log \log x}$

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

Пол Эрдёш дал доказательство ^[11] , которое также опирается на фундаментальную теорему арифметики. Каждое положительное целое число имеет уникальное разложение на свободное от квадратов число r и квадратное число s ² . Например, 75 600 = 2 ⁴ 3 ³ 5 ² 7 ¹ = 21 ⋅ 60 ² .

Пусть N — положительное целое число, а k — количество простых чисел, меньших или равных N. Назовем эти простые числа p ₁ , ... , p _k . Любое положительное целое число a, которое меньше или равно N, можно записать в виде

$${\displaystyle a=\left(p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}\right)s^{2},}$$

где каждый e _i равен 0 или 1. Существует 2 ^k способов формирования свободной от квадратов части a . И s ² может быть не более N , поэтому s ≤ √ N. Таким образом, в этой форме можно записать не более 2 ^k √ N чисел. Другими словами,

$${\displaystyle N\leq 2^{k}{\sqrt {N}}.}$$

Или, переставляя k , число простых чисел, меньших или равных N , больше или равно ⁠1/2⁠ log ₂ N. Поскольку N было произвольным, k может быть сколь угодно большим, если выбрать N соответствующим образом.

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

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

Определите топологию целых чисел , называемую равномерно распределенной целочисленной топологией , объявив подмножество открытым множеством тогда и только тогда, когда оно является либо пустым множеством , либо объединением арифметических последовательностей (для ), где ${\textstyle \mathbb {Z} }$ ${\textstyle U\subseteq \mathbb {Z} }$ ${\textstyle \emptyset }$ ${\textstyle S(a,b)}$ ${\textstyle a\neq 0}$

$${\displaystyle S(a,b)=\{an+b\mid n\in \mathbb {Z} \}=a\mathbb {Z} +b.}$$

Тогда противоречие следует из свойства, что конечный набор целых чисел не может быть открытым, и свойства, что базисные наборы являются как открытыми, так и закрытыми , поскольку ${\textstyle S(a,b)}$

$${\displaystyle \mathbb {Z} \setminus \{-1,+1\}=\bigcup _{p{\text{ prime}}}S(p,0)}$$

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

Последние доказательства

Доказательство с использованием принципа включения-исключения

Хуан Пабло Пинаско написал следующее доказательство. ^[13]

Пусть p ₁ , ...,  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 и позволив x  → ∞, получаем

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

Если не существует других простых чисел, кроме p ₁ , ...,  p _N , то выражение в (1) равно  , а выражение в (2) равно 1, но очевидно, что выражение в (3) не равно 1. Следовательно, должно быть больше простых чисел, чем   p ₁ , ...,  p _N . ${\displaystyle \lfloor x\rfloor }$

Доказательство с использованием формулы Лежандра

В 2010 году Джунхо Питер Ванг опубликовал следующее доказательство от противного. ^[14] Пусть 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}}\leq k.}$$

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

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

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

Доказательство построением

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

Доказательство с использованием метода несжимаемости

Предположим, что существует только k простых чисел ( p ₁ , ..., p _k ). По фундаментальной теореме арифметики любое положительное целое число n может быть представлено как

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

где неотрицательные целые показатели степеней e _i вместе со списком простых чисел конечного размера достаточны для восстановления числа. Так как для всех i , то следует, что для всех i (где обозначает логарифм по основанию 2). Это дает кодировку для n следующего размера (используя нотацию big O ): бит. Это гораздо более эффективное кодирование, чем представление n непосредственно в двоичном виде, которое занимает биты. Установленный результат в сжатии данных без потерь гласит, что в общем случае невозможно сжать N бит информации в меньшее, чем N бит. Представление выше значительно нарушает это, когда n достаточно велико, так как . Следовательно, количество простых чисел не должно быть конечным. ^[16] ${\displaystyle p_{i}\geq 2}$ ${\displaystyle e_{i}\leq \lg n}$ ${\displaystyle \lg }$ ${\displaystyle O({\text{prime list size}}+k\lg \lg n)=O(\lg \lg n)}$ ${\displaystyle N=O(\lg n)}$ ${\displaystyle \lg \lg n=o(\lg n)}$

Доказательство с использованием четно-нечетного аргумента

Ромео Мештрович использовал четно-нечетный аргумент, чтобы показать, что если количество простых чисел не бесконечно, то 3 является наибольшим простым числом, противоречие. ^[17]

Предположим, что — все простые числа. Рассмотрите и заметьте, что по предположению все положительные целые числа, взаимно простые с ним, находятся в наборе . В частности, является взаимно простым с и, следовательно, является . Однако это означает, что — нечетное число в наборе , поэтому , или . Это означает, что должно быть наибольшим простым числом, что является противоречием. ${\displaystyle p_{1}=2<p_{2}=3<p_{3}<\cdots <p_{k}}$ ${\displaystyle P=3p_{3}p_{4}\cdots p_{k}}$ ${\displaystyle S=\{1,2,2^{2},2^{3},\dots \}}$ ${\displaystyle 2}$ ${\displaystyle P}$ ${\displaystyle P-2}$ ${\displaystyle P-2}$ ${\displaystyle S}$ ${\displaystyle P-2=1}$ ${\displaystyle P=3}$ ${\displaystyle 3}$

Вышеприведенное доказательство продолжает работать, если заменить на любое простое число с , произведение становится и четный против нечетного аргумента заменяется на делимый против не делимого на аргумент. Результирующее противоречие заключается в том, что должно одновременно быть равно и быть больше , ^[a], что невозможно. ${\displaystyle 2}$ ${\displaystyle p_{j}}$ ${\displaystyle j\in \{1,2,\dots ,k-1\}}$ ${\displaystyle P}$ ${\displaystyle p_{1}p_{2}\cdots p_{j-1}\cdot p_{j+1}\cdots p_{k}}$ ${\displaystyle p_{j}}$ ${\displaystyle P-p_{j}}$ ${\displaystyle 1}$ ${\displaystyle 1}$

Более сильные результаты

Теоремы этого раздела одновременно влекут за собой теорему Евклида и другие результаты.

Теорема Дирихле об арифметических прогрессиях

Теорема Дирихле утверждает, что для любых двух положительных взаимно простых целых чисел a и  d существует бесконечно много простых чисел вида a  +  nd , где n также является положительным целым числом. Другими словами, существует бесконечно много простых чисел, которые сравнимы с a по модулю d .

Теорема о простых числах

Пусть π ( x ) будет функцией подсчета простых чисел , которая дает количество простых чисел, меньших или равных x , для любого действительного числа  x . Тогда теорема о простых числах утверждает, что x / log x является хорошим приближением к π ( x ) , в том смысле, что предел частного двух функций π ( x ) и x / log x при неограниченном увеличении x равен 1:

$${\displaystyle \lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\log(x)}}=1.}$$

Используя асимптотическую запись, этот результат можно переформулировать как

$${\displaystyle \pi (x)\sim {\frac {x}{\log x}}.}$$

Это приводит к теореме Евклида, поскольку ${\displaystyle \lim _{x\rightarrow \infty }{\frac {x}{\log x}}=\infty .}$

Теорема Бертрана–Чебышева

В теории чисел постулат Бертрана — это теорема, утверждающая, что для любого целого числа всегда существует по крайней мере одно простое число такое, что Эквивалентно, записывая для функции подсчета простых чисел (количества простых чисел, меньших или равных ), теорема утверждает, что для всех . ${\displaystyle n>1}$ $${\displaystyle n<p<2n.}$$ ${\displaystyle \pi (x)}$ ${\displaystyle x}$ ${\textstyle \pi (x)-\pi ({\tfrac {x}{2}})\geq 1}$ ${\displaystyle x\geq 2}$

Это утверждение было впервые высказано в 1845 году Жозефом Бертраном ^[18] (1822–1900). Сам Бертран проверил свое утверждение для всех чисел в интервале [2, 3 × 10 ⁶ ]. Его предположение было полностью доказано Чебышевым ( 1821–1894 ) в 1852 году ^[19] , поэтому постулат также называется теоремой Бертрана–Чебышёва или теоремой Чебышёва .

Примечания

1. В доказательстве выше (с ) это противоречие выглядело бы следующим образом: . В более общем доказательстве противоречие было бы: ; то есть, заменяет и коэффициент при является наименьшим простым числом в . ${\displaystyle j=1,p_{j}=2}$ ${\displaystyle 1=P-2>3p_{k}-2>2>1}$ ${\displaystyle 1=P-p_{j}>2p_{k}-p_{j}>p_{j}>1}$ ${\displaystyle p_{j}}$ ${\displaystyle 2}$ ${\displaystyle p_{k}}$ ${\displaystyle P}$

Ссылки

1. Джеймс Уильямсон (переводчик и комментатор), «Начала Евклида» с диссертациями , Clarendon Press , Оксфорд, 1782, стр. 63.
2. Оре, Ойстейн (1988) [1948], Теория чисел и ее история , Довер, стр. 65
3. В общем случае для любых целых чисел a , b , c если и , то . Для получения дополнительной информации см. Делимость . ${\displaystyle a\mid b}$ ${\displaystyle a\mid c}$ ${\displaystyle a\mid (b-c)}$
4. Точная формулировка утверждения Евклида такова: «Простых чисел больше, чем любое предполагаемое множество простых чисел».
5. Кац, Виктор Дж. (1998), История математики/Введение (2-е изд.), Эддисон Уэсли Лонгман, стр. 87
6. Майкл Харди и Кэтрин Вудголд, «Prime Simplicity», Mathematical Intelligencer , том 31, номер 4, осень 2009 г., страницы 44–52.
7. Францен, Торкель (2004), Неисчерпаемость: неисчерпывающее рассмотрение , AK Peters, Ltd, стр. 101
8. Босток, Линда; Чандлер, Сюзанна; Рурк, К. (2014-11-01). Дальнейшая чистая математика . Нельсон Торнс. стр. 168. ISBN 9780859501033.
9. Теоремы 7 и их следствия 1 и 2 в: Леонард Эйлер. «Вариативные наблюдения около бесконечной серии» . Commentarii Academiae scientiarum Imperialis Petropolitanae 9, 1744, стр. 160–188. английский перевод
10. В своей «Истории теории чисел» (т. 1, стр. 413) Диксон ссылается на это доказательство, а также на другое, цитируя страницу 235 другой работы Эйлера: Introductio in Analysin Infinitorum. Tomus Primus. Bousquet, Lausanne 1748. [1]. Там (§ 279) Эйлер фактически заново формулирует гораздо более сильную теорему 19 (описанную ниже) в статье своего прежнего доказательства.
11. Havil, Julian (2003). Гамма: исследование константы Эйлера . Princeton University Press. стр. 28–29. ISBN 0-691-09983-9.
12. Фюрстенберг, Гарри (1955). «О бесконечности простых чисел». American Mathematical Monthly . 62 (5): 353. doi :10.2307/2307043. JSTOR  2307043. MR  0068566.
13. Хуан Пабло Пинаско, «Новые доказательства теорем Евклида и Эйлера», American Mathematical Monthly , том 116, номер 2, февраль 2009 г., страницы 172–173.
14. Джунхо Питер Ванг, «Еще одно доказательство бесконечности простых чисел», American Mathematical Monthly , том 117, номер 2, февраль 2010 г., стр. 181.
15. Сайдак, Филип (декабрь 2006 г.). «Новое доказательство теоремы Евклида». American Mathematical Monthly . 113 (10): 937–938. doi :10.2307/27642094. JSTOR  27642094.
16. Шен, Александр (2016), Колмогоровская сложность и алгоритмическая случайность (PDF) , AMS, стр. 245
17. Мештрович, Ромео (13 декабря 2017 г.). «Очень короткое доказательство бесконечности простых чисел». The American Mathematical Monthly . 124 (6): 562. doi :10.4169/amer.math.monthly.124.6.562 . Получено 30 июня 2024 г.
18. Бертран, Жозеф (1845), «Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme.», Journal de l'École Royale Polytechnique (на французском языке), 18 (Cahier 30) : 123–140.
19. Чебычев, П. (1852), «Mémoire sur les nombres premiers». (PDF) , Journal de mathématiques pures et appliquées , Série 1 (на французском языке): 366–390.. (Доказательство постулата: 371–382). См. также Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, стр. 15–33, 1854 г.

Внешние ссылки

• Вайсштейн, Эрик В. «Теорема Евклида». MathWorld .
• «Начала» Евклида, книга IX, предложение 20 (доказательство Евклида на сайте Дэвида Джойса в Университете Кларка)