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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle rs^{2}}$ ,

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

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

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

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

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

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

2006 року Філіп Сайдак надав таке конструктивне доведення, яке не використовує доведення до абсурду^[5] або лему Евкліда (про те, що, якщо просте число p ділить ab, воно має ділити або a, або b).

Оскільки кожне натуральне число (${\displaystyle >1}$) має щонайменше один простий множник, а два послідовні числа ${\displaystyle n}$ і ${\displaystyle (n+1)}$ не мають спільного дільника, добуток ${\displaystyle n}$ і ${\displaystyle (n+1)}$ має більше різних простих дільників, ніж саме число ${\displaystyle 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 року Хуан Пабло Піаско запропонував таке доведення^[6].

Нехай ${\displaystyle p_{1},\dots ;p_{N}}$ — найменші ${\displaystyle N}$ простих чисел. Тоді, згідно з принципом включень-виключень, кількість додатних цілих чисел, що не перевищують ${\displaystyle 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}}}$

Поділивши на ${\displaystyle x}$ і спрямувавши ${\displaystyle x\to \infty }$, маємо

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

Якщо ніяких інших простих чисел, відмінних від ${\displaystyle p_{1},\dots ,p_{N}}$, не існує, вираз у (1) дорівнює ${\displaystyle \lfloor x\rfloor }$ і вираз (2) дорівнює 1, проте ясно, що вираз (3) одиниці не дорівнює. Таким чином, повинні існувати прості числа, відмінні від ${\displaystyle p_{1},\dots ,p_{N}}$.

2010 року Джун Хо Пітер Ванг опублікував таке доведення від супротивного^[7]. Нехай k — деяке натуральне число. Тоді, згідно з формулою Лежандра^[en]

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

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

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

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

Подання формули Лейбніца для ${\displaystyle \pi }$ у вигляді добутку Ейлера^[en] дає^[8]

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

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

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

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

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

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

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

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

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

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

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

• 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