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

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

Доказательство Евклида [ править ]

Евклид предложил доказательство, опубликованное в его работе «Элементы» (книга 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 1, ... q n$ — все простые числа». Однако, поскольку это предположение даже не используется в доказательстве, переформулировка бессмысленна». ^[7]

Вариации [ править ]

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

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

Доказательство Эйлера [ править ]

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

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

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

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

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

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

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

сходится к конечному значению 2, и, следовательно, простых чисел больше, чем квадратов («sequitur infinities plures esse numeros primos»). Это доказывает теорему Евклида. ^[10]

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

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

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

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

Доказательство Эрдеша [ править ]

Пол Эрдеш предоставил доказательство ^[11]это также опирается на фундаментальную теорему арифметики. Каждое положительное целое число имеет уникальную факторизацию на свободное от квадратов число $r$ и квадратное число $s. 2$ . Например, $75 600 = 2 4335271 = 21 \cdot 60 2$ .

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

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

где каждый $e i$ равен $0$ или $1$ . Есть $2 к$ способы образования бесквадратной $части$ . И $с 2$ может быть не более $N$ поэтому $s \leq \sqrt N.$ , Таким образом, не более $2 к \sqrt N$ В таком виде можно записать чисел. Другими словами,

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

Или, переставив, $k$ , количество простых чисел, меньшее или равное $N$ , больше или равно $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/2 лог 2 Н.$ Поскольку $N$ было произвольным, $k$ может быть сколь угодно большим, если выбрать $N$ соответствующим образом.

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

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

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

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

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

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

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

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

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

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

Пусть p ₁ , ..., p _N — наименьшие N простых чисел. Тогда согласно принципу включения-исключения количество натуральных чисел, меньших или равных x , которые делятся на одно из этих простых чисел, равно

{\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 → ∞, получим

\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)

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

1-\prod _{i=1}^{N}\left(1-{\frac {1}{p_{i}}}\right).\qquad (3)

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

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

В 2010 году Чуно Питер Ван опубликовал следующее доказательство от противного. ^[14]Пусть k — любое положительное целое число. Тогда по формуле Лежандра (иногда приписываемой де Полиньяку )

k!=\prod _{p{\text{ prime}}}p^{f(p,k)}

где

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

f(p,k)<{\frac {k}{p}}+{\frac {k}{p^{2}}}+\cdots ={\frac {k}{p-1}}\leq k.

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

\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 можно представить в виде

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

где неотрицательных целых показателей e _i вместе со списком простых чисел конечного размера достаточно для восстановления числа. С

p_{i}\geq 2

для всех i отсюда следует, что

e_{i}\leq \lg n

для всех я (где

\lg

обозначает логарифм по основанию 2). Это дает кодировку для n следующего размера (с использованием обозначения big O ):

O({\text{prime list size}}+k\lg \lg n)=O(\lg \lg n)

биты.

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

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

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

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

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

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

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

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

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

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

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

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

В теории чисел , постулат Бертрана — это теорема утверждающая, что для любого целого числа $n>1$ , всегда существует хотя бы одно простое число такое, что

n<p<2n.

Теорему Бертрана – Чебышева также можно сформулировать как связь с $\pi (x)$ , где $\pi (x)$ — функция подсчета простых чисел (количество простых чисел, меньшее или равное $x\,$ ):

\pi (x)-\pi ({\tfrac {x}{2}})\geq 1,

для всех

x\geq 2.

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

Примечания и ссылки [ править ]

^ Джеймс Уильямсон (переводчик и комментатор), Элементы Евклида, с диссертациями , Clarendon Press , Оксфорд, 1782, стр. 63.
^ Оре, Эйстейн (1988) [1948], Теория чисел и ее история , Дувр, с. 65
^ В общем, для любых целых чисел a , b , c , если $a\mid b$ и $a\mid c$ , затем $a\mid (b-c)$ . Дополнительную информацию см. в разделе Делимость .
^ Точная формулировка утверждения Евклида: «Простые числа более многочисленны, чем любое предполагаемое множество простых чисел».
^ Кац, Виктор Дж. (1998), История математики / Введение (2-е изд.), Аддисон Уэсли Лонгман, стр. 87
^ Майкл Харди и Кэтрин Вудголд, «Prime Simplicity», Mathematical Intelligencer , том 31, номер 4, осень 2009 г., страницы 44–52.
^ Франзен, Торкель (2004), Неисчерпаемость: неисчерпывающее лечение , AK Peters, Ltd, стр. 101
^ Босток, Линда; Чендлер, Сюзанна; Рурк, К. (1 ноября 2014 г.). Дальше чистая математика . Нельсон Торнс. п. 168. ИСБН 9780859501033 .
^ Теоремы 7 и их следствия 1 и 2 в: Леонард Эйлер. Различные наблюдения о бесконечных рядах. Commentarii Academiae scientiarum Imperialis Petropolitanae 9, 1744, стр. 160–188. [1 ] (Оригинал) [2] . (английская версия перевода)
^ В своей «Истории теории чисел» (том 1, стр. 413) Диксон ссылается на это доказательство, а также на другое, цитируя страницу 235 другой работы Эйлера: Introductio in Analysin Infinitorum. Томус Примус. Буске, Лозанна, 1748 год. [3] . Там (§ 279) Эйлер фактически переформулирует гораздо более сильную теорему 19 (описанную ниже) в статье своего предыдущего доказательства.
^ Хэвил, Джулиан (2003). Гамма: изучение постоянной Эйлера . Издательство Принстонского университета. стр. 28–29 . ISBN 0-691-09983-9 .
^ Фюрстенберг, Гарри (1955). «О бесконечности простых чисел». Американский математический ежемесячник . 62 (5): 353. дои : 10.2307/2307043 . JSTOR 2307043 . МР 0068566 .
^ Хуан Пабло Пинаско, «Новые доказательства теорем Евклида и Эйлера», American Mathematical Monthly , том 116, номер 2, февраль 2009 г., страницы 172–173.
^ Джуно Питер Ванг, «Еще одно доказательство бесконечности простых чисел», American Mathematical Monthly , том 117, номер 2, февраль 2010 г., страница 181.
^ Сайдак, Филип (декабрь 2006 г.). «Новое доказательство теоремы Евклида» . Американский математический ежемесячник . 113 (10): 937–938. дои : 10.2307/27642094 . JSTOR 27642094 .
^ Шен, Александр (2016), Колмогоровская сложность и алгоритмическая случайность (PDF) , AMS, стр. 245
^ Бертран, Жозеф (1845), «Память о количестве значений, которые может принимать функция, когда мы переставляем содержащиеся в ней буквы». , Journal de l’École Royale Polytechnique (на французском языке), 18 (Cahier 30): 123–140 .
^ Чебышев П. (1852), «Память о простых числах». (PDF) , Журнал чистой и прикладной математики , серия 1 (на французском языке): 366–390 . (Доказательство постулата: 371–382). См. также «Воспоминания об Императорской Академии наук Петербурга», т. 1, с. 7, с. 15–33, 1854 г.

Внешние ссылки [ править ]

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

[1] Джеймс Уильямсон (переводчик и комментатор), Элементы Евклида, с диссертациями , Clarendon Press , Оксфорд, 1782, стр. 63.

[2] Оре, Эйстейн (1988) [1948], Теория чисел и ее история , Дувр, с. 65

[3] В общем, для любых целых чисел a , b , c , если $a\mid b$ и $a\mid c$ , затем $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] Босток, Линда; Чендлер, Сюзанна; Рурк, К. (1 ноября 2014 г.). Дальше чистая математика . Нельсон Торнс. п. 168. ИСБН 9780859501033 .

[9] Теоремы 7 и их следствия 1 и 2 в: Леонард Эйлер. Различные наблюдения о бесконечных рядах. Commentarii Academiae scientiarum Imperialis Petropolitanae 9, 1744, стр. 160–188. [1 ] (Оригинал) [2] . (английская версия перевода)

[10] В своей «Истории теории чисел» (том 1, стр. 413) Диксон ссылается на это доказательство, а также на другое, цитируя страницу 235 другой работы Эйлера: Introductio in Analysin Infinitorum. Томус Примус. Буске, Лозанна, 1748 год. [3] . Там (§ 279) Эйлер фактически переформулирует гораздо более сильную теорему 19 (описанную ниже) в статье своего предыдущего доказательства.

[Havil-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), «Память о количестве значений, которые может принимать функция, когда мы переставляем содержащиеся в ней буквы». , Journal de l’École Royale Polytechnique (на французском языке), 18 (Cahier 30): 123–140 .

[18] Чебышев П. (1852), «Память о простых числах». (PDF) , Журнал чистой и прикладной математики , серия 1 (на французском языке): 366–390 . (Доказательство постулата: 371–382). См. также «Воспоминания об Императорской Академии наук Петербурга», т. 1, с. 7, с. 15–33, 1854 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]