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

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

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

Доказательства

Евклид

Евклид предложил доказательство, опубликованное в его труде «Начала» (книга 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\mathrm {\,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 \pi (x)}$ ${\displaystyle x\,}$

$${\displaystyle \forall x\geq 2.\pi (x)-\pi ({\tfrac {x}{2}})\geq 1}$$

Это утверждение было впервые высказано в 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 (доказательство Евклида на сайте Дэвида Джойса в Университете Кларка)