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

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

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

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

Евклид предложил доказательство, опубликованное в его работе «Начала» (книга 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 , поскольку оно является произведением всех из них. Следовательно, н ! + 1 не делится ни на одно из целых чисел от 2 до n включительно (при делении на каждое из них получается остаток 1). Следовательно, н ! + 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, и, следовательно, простых чисел больше, чем квадратов («sequitur infinities plures esse numeros primos»). Это доказывает теорему Евклида. ^[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 . Существует 2k ^{способов} образовать свободную от квадратов часть . И s ² может быть не более N , поэтому s ≤ √ N. Таким образом, в такой форме можно записать не более 2 ^k √ N чисел. Другими словами,

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

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

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

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

Определите топологию целых чисел Z , называемую равноотстоящей целочисленной топологией , объявив подмножество U  ⊆  Z открытым множеством тогда и только тогда, когда это либо пустое множество , ∅, либо объединение арифметических последовательностей S ( a ,  b ) (при a  ≠ 0), где

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

Тогда противоречие следует из того свойства, что конечное множество целых чисел не может быть открытым, и того свойства, что базисные множества 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 _iiinобозначения big O ${\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)}$биты.

Это гораздо более эффективное кодирование, чем непосредственное представление n в двоичном формате, требующее битов. Установленный результат сжатия данных без потерь гласит, что обычно невозможно сжать N бит информации менее чем в N бит. Представление, приведенное выше, нарушает это правило, когда n достаточно велико, поскольку . Следовательно, количество простых чисел не должно быть конечным. ^[16] ${\displaystyle N=O(\lg n)}$ ${\displaystyle \lg \lg n=o(\lg n)}$

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

Из теорем этого раздела одновременно вытекают теорема Евклида и другие результаты.

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

Теорема Дирихле утверждает, что для любых двух положительных взаимно простых целых чисел a и  d существует бесконечно много простых чисел вида a  +  nd , где n также является положительным целым числом. Другими словами, существует бесконечно много простых чисел , конгруэнтных модулю 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 \pi (x)-\pi ({\tfrac {x}{2}})\geq 1,}$для всех ${\displaystyle x\geq 2.}$

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

Примечания и ссылки

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-е изд.), Аддисон Уэсли Лонгман, стр. 10. 87
6. Майкл Харди и Кэтрин Вудголд, «Prime Simplicity», Mathematical Intelligencer , том 31, номер 4, осень 2009 г., страницы 44–52.
7. Францен, Торкель (2004), Неисчерпаемость: неисчерпывающее лечение , AK Peters, Ltd, стр. 101
8. Босток, Линда; Чендлер, Сюзанна; Рурк, К. (1 ноября 2014 г.). Дальше чистая математика . Нельсон Торнс. п. 168. ИСБН 9780859501033.
9. Теоремы 7 и их следствия 1 и 2 в: Леонард Эйлер. Различные наблюдения около серии infinitas. Commentarii academiae scientiarum Petropolitanae 9, 1744, стр. 160–188. [1]. (Оригинал) [2]. (английская версия перевода)
10. В своей «Истории теории чисел» (том 1, стр. 413) Диксон ссылается на это доказательство, а также на другое, цитируя страницу 235 другой работы Эйлера: Introductio in Analysin Infinitorum. Томус Примус. Буске, Лозанна, 1748 г. [3]. Там (§ 279) Эйлер фактически переформулирует гораздо более сильную теорему 19 (описанную ниже) в статье своего предыдущего доказательства.
11. Хэвил, Джулиан (2003). Гамма: изучение постоянной Эйлера . Издательство Принстонского университета. стр. 28–29. ISBN 0-691-09983-9.
12. Фюрстенберг, Гарри (1955). «О бесконечности простых чисел». Американский математический ежемесячник . 62 (5): 353. дои : 10.2307/2307043. JSTOR  2307043. МР  0068566.
13. Хуан Пабло Пинаско, «Новые доказательства теорем Евклида и Эйлера», American Mathematical Monthly , том 116, номер 2, февраль 2009 г., страницы 172–173.
14. Джуно Питер Ванг, «Еще одно доказательство бесконечности простых чисел», American Mathematical Monthly , том 117, номер 2, февраль 2010 г., страница 181.
15. Сайдак, Филип (декабрь 2006 г.). «Новое доказательство теоремы Евклида». Американский математический ежемесячник . 113 (10): 937–938. дои : 10.2307/27642094. JSTOR  27642094.
16. Шен, Александр (2016), Колмогоровская сложность и алгоритмическая случайность (PDF) , AMS, стр. 245
17. Бертран, Жозеф (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.
18. Чебычев, П. (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 г.

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

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