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

Теорема Евкліда — фундаментальний елемент теорії чисел. Вона стверджує, що для будь-якого скінченного списку простих чисел знайдеться просте число, яке не увійшло до цього списку (тобто існує безліч простих чисел).

Є кілька відомих доведень цієї теореми.

Доведення Евкліда

Найстаріше відоме доведення цього факту навів Евклід у «Началах» (книга IX, твердження 20). При цьому Евклід не використовує поняття нескінченності, а доводить це твердження в такому формулюванні: простих чисел більше, ніж будь-яка вибрана їх множина.

Евклід доводить це так.

Припустимо, що дано деякий скінченний список простих чисел $a,b,\dots z$. Евклід доводить, що існує просте число, яке не входить до цього списку.

Нехай $P$ — найменше спільне кратне цих чисел, $P=a*b*...*z$.

Евклід розглядає число $Q=P+1$. Якщо $Q$ — просте, то знайдено просте число, яке не входить до цього списку ${a,b,....z}$ (оскільки воно більше від кожного числа зі списку).

Якщо ж $Q$ не є простим, то існує деяке просте число $x$, на яке число $Q$ ділиться націло. Але $x$ не може бути одночасно і дільником $Q$, і елементом списку ${a,b,....z}$ оскільки тоді при діленні $Q$ на $x$ була б остача, не рівна нулю. Отже, існує просте число $x$, яке не входить до жодного (скінченного) списку простих чисел ${a,b,....z}$.

Часто при викладі доведення теореми Евкліда починають із розгляду одразу множини всіх простих чисел (у припущенні, що ця множина містить скінченну кількість елементів), і далі ведуть доведення теореми від супротивного. Хоча таке доведення також можливе, оригінальне міркування Евклід проводить елегантніше — саме для будь-якого скінченного набору простих чисел, і доводить, що має існувати якесь просте число, яке не входить до цього (будь-якого) набору простих чисел.

Коротка форма доведення Евкліда:

Нехай дано скінченний набір простих чисел. Покажемо, що існує просте число, яке не входить до цього набору. Перемножимо числа з цього набору та додамо одиницю. Отримане число не ділиться на жодне число з цього набору, тому що остача від ділення на будь-яке з них дає одиницю. Значить, число має ділитися на просте число, не включене в цей набір.

Варіація доведення Евкліда з використанням факторіалу

Інші варіації доведення Евкліда використовують факторіал: n! ділиться на будь-яке ціле від 2 до n, оскільки він є їх добутком. Отже, n! + 1 не ділиться на жодне натуральне число від 2 до n включно (при діленні на будь-яке з цих чисел отримаємо остачу 1). Отже, n! + 1 або є простим, або ділиться на просте число, більше ніж n. У будь-якому випадку ми маємо для будь-якого натурального числа n щонайменше одне просте число, більше від n . Звідси робимо висновок, що простих чисел нескінченно багато.

Евклідові числа

Деякі пов'язані доведення цієї теореми використовують так звані евклідові числа (послідовність A006862 з Онлайн енциклопедії послідовностей цілих чисел, OEIS): $E_{n}=p_{n}\#+1$, де $p_{n}\#$ — добуток перших $n$ простих чисел (прайморіал). При цьому, формально кажучи, доведення, яке навів Евклід, не використовує цих чисел. Як сказано вище, Евклід показує, що для будь-якого скінченного набору простих чисел (не обов'язково перших $n$ простих чисел) існує просте число, яке не включене в цей набір.

Доведення Ейлера

Інше доведення, як е запропонував Леонард Ейлер, спирається на основну теорему арифметики, яка стверджує, що будь-яке ціле число має єдиний розклад на прості множники. Якщо позначити через P множину всіх простих чисел, можна записати рівність:

$\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}}.$

Перша рівність виходить із формули для геометричного ряду в кожному множнику добутку. Друга рівність виходить перестановкою місцями добутку та суми:

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

У результаті будь-який добуток простих чисел з'являється у формулі лише один раз, а тоді, відповідно до основної теореми арифметики, сума дорівнює сумі за всіма натуральними числами.

Сума справа є розбіжним гармонічним рядом, так що добуток зліва повинен також бути розбіжним, що неможливо, якщо кількість елементів у множині P скінченна.

З цього доведення Ейлер отримав сильніше твердження, ніж теорема Евкліда, а саме розбіжність суми обернених значень простих чисел.

Доведення Ердеша

Пал Ердеш надав третє доведення, яке також спирається на основну теорему арифметики. Спочатку звернемо увагу на те, що будь-яке натуральне число n можна подати у вигляді

$rs^{2}$ ,

де $r$ є вільним від квадратів (не ділиться на жоден повний квадрат). Ми можемо взяти як $s^{2}$ найбільший квадрат, який ділить $n$, а тоді $r=n/{s^{2}}$. Тепер припустимо, що є лише скінченна кількість простих чисел та позначимо цю кількість простих чисел буквою $k$. Оскільки кожне просте число може з'явитися в розкладі будь-якого вільного від квадратів числа лише раз, згідно з основною теоремою арифметики, є тільки $2^{k}$ вільних від квадратів чисел.

Тепер зафіксуємо деяке натуральне число $N$ і розглянемо натуральні числа між 1 та $N$. Кожне з цих чисел можна записати у вигляді $rs^{2}$ де $r$ — вільне від квадратів число, а $s^{2}$ є квадратом:

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

У списку $N$ різних чисел і кожне з них є добутком вільного від квадратів числа на квадрат, що не перевищує $N$. Є $\lfloor {\sqrt {N}}\rfloor$ таких квадратів. Тепер утворюємо всі можливі добутки всіх квадратів, що не перевищують $N$, на всі вільні від квадратів числа. Є рівно $2^{k}\lfloor {\sqrt {N}}\rfloor$ таких чисел, всі вони різні і включають усі числа з нашого списку, а можливо, й більше. Отже, $2^{k}\lfloor {\sqrt {N}}\rfloor \geqslant N$. Тут $\lfloor {x}\rfloor$ означає цілу частину.

Оскільки нерівність не виконується для досить великого $N$, простих чисел має бути нескінченно багато.

Доведення Фюрстенберга

1955 року Гілель Фюрстенберг опублікував нове доведення нескінченності кількості простих чисел, використовуючи топологію точкових множин.

Деякі свіжі доведення

Сайдак

2006 року Філіп Сайдак надав таке конструктивне доведення, яке не використовує доведення до абсурду або лему Евкліда (про те, що, якщо просте число 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}, · · ·дає послідовність необмежено розширюваних множин простих чисел.

Пінаско

2009 року Хуан Пабло Піаско запропонував таке доведення.

Нехай $p_{1},\dots ;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\to \infty$, маємо

$\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_{1},\dots ,p_{N}$, не існує, вираз у (1) дорівнює $\lfloor x\rfloor$ і вираз (2) дорівнює 1, проте ясно, що вираз (3) одиниці не дорівнює. Таким чином, повинні існувати прості числа, відмінні від $p_{1},\dots ,p_{N}$.

Ванг

2010 року Джун Хо Пітер Ванг опублікував таке доведення від супротивного. Нехай 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}}\leqslant k.$

Але якщо існує тільки скінченна кількість простих чисел,

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

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

Доведення, що використовує ірраціональність $\pi$

Подання формули Лейбніца для $\pi$ у вигляді добутку Ейлера дає

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

Чисельниками є непарні прості числа, а кожен знаменник є найближчим до чисельника числом, кратним 4.

Якби простих чисел була скінченна кількість, ця формула дала б для $\pi$ раціональне подання, знаменник якого є добутком усіх чисел, що суперечить ірраціональності $\pi$.

Доведення з використанням теорії інформації

Олександр Шень та інші надали доведення з використанням метод нестисливості та колмогоровську складність: Припустимо, що є тільки $k$ простих чисел ($p_{1},\dots ,p_{k}$). Відповідно до основної теореми арифметики, будь-яке натуральне число $n$ подаване у вигляді

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

де невід'ємні цілі числа $e_{i}$ разом зі списком скінченного розміру простих чисел достатні для реконструкції числа. Оскільки $p_{i}\geqslant 2$ для всіх $i$, звідси випливає, що всі $e_{i}\leqslant \log n$ (де $\log$ означає логарифм за основою 2).

Це дає метод кодування для $n$ такого розміру (використовуючи нотацію «O велике»):

$O({\text{prime list size}}+k\log \log n)=O(\log \log n)$ біт.

Це значно ефективніше кодування, ніж подання $n$ безпосередньо в двійковому коді, яке вимагає $N=O(\log n)$ біт. Установлений результат про стиснення без втрат стверджує, що немає алгоритму стиснення без втрат $N$ біт інформації у менш ніж $N$ біт. Наведене вище подання порушує це твердження, оскільки за досить великих $n$ $\log \log n=o(\log n)$.

Отже, простих чисел нескінченно багато.

Асимптотика розподілу простих чисел

Теорема про розподіл простих чисел стверджує, що кількість простих чисел менших від $n$, що позначається як $\pi (n)$, зростає як $n/\ln(n)$.

Див. також

• Теорема Діріхле про арифметичні прогресії
• Теорема про розподіл простих чисел

Література

• Начала Евклида / Перевод с греческого и комментарии Д. Д. Мордухай-Болтовского при редакционном участии М. Я. Выгодского и И. Н. Веселовского. — М.—Л. : ГТТИ, 1949—1951. — (Классики естествознания)
• Michael Hardy, Catherine Woodgold. Prime Simplicity // The Mathematical Intelligencer. — 2009. — Vol. 31, no. 4. — P. 44—52..
• The Elements of Euclid, With Dissertations / James Williamson (переклад і коментарі) // Clarendon Press. — Oxford, 1782. — С. 63.
• Linda. Further Pure Mathematics. — Nelson Thornes, 2014. — С. 168. — ISBN 9780859501033.
• Junho Peter Whang. Another Proof of the Infinitude of the Prime Numbers // American Mathematical Monthly. — 2010. — Т. 117, № 2 (February). — С. 181.
• Filip Saidak. A New Proof of Euclid's Theorem // American Mathematical Monthly. — 2006. — Т. 113, вип. 10 (December). — DOI:10.2307/27642094.
• Lokenath Debnath. The Legacy of Leonhard Euler: A Tricentennial Tribute. — World Scientific, 2010. — С. 214. — ISBN 9781848165267.
• Верещагин Н. К., Успенский В. А., Шень О.. Колмогоровская сложность и алгоритмическая случайность. — Издательство Московского центра непрерывного математического образования, 2013.
• Juan Pablo Pinasco. New Proofs of Euclid's and Euler's theorems // American Mathematical Monthly. — 2009. — Т. 116, № 2 (February).

Посилання

• Weisstein, Eric W. Теорема Евкліда(англ.) на сайті Wolfram MathWorld.
• Euclid's Elements, Book IX, Prop. 20 (Euclid's proof, on David Joyce's website at Clark University)
• 125 proofs of Euclid's theorem