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

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

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

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

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

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

Припустимо, що дано деякий скінченний список простих чисел ${\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}}$.

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

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

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

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

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

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

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

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

Інше доведення, як е запропонував Леонард Ейлер, спирається на основну теорему арифметики, яка стверджує, що будь-яке ціле число має єдиний розклад на прості множники. Якщо позначити через 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}}}$

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

Сума справа є (розбіжним) гармонічним рядом, так що добуток зліва повинен також бути розбіжним, що неможливо, якщо кількість елементів у множині 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 року Філіп Сайдак надав таке конструктивне доведення, яке не використовує доведення до абсурду або лему Евкліда (про те, що, якщо просте число 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 року Хуан Пабло Піаско запропонував таке доведення.

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

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

${\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] та колмогоровську складність: Припустимо, що є тільки ${\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)}$.

Див. також

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

Коментарі

1. Ця рівність є окремим випадком формули для ^{[en] [en]}.

Примітки

1. Начала Евклида та 1949—1951, с. 89, Книга IX, Предложение 20.
2. Hardy, Michael; Woodgold, Catherine. Prime Simplicity // The Mathematical Intelligencer. — 2009. — Vol. 31, no. 4. — P. 44—52. — DOI:10.1007/s00283-009-9064-8.(англ.)
3. Bostock, Chandler, Rourke, 2014, с. 168.
4. Romeo Mestrovic. Euclid's theorem on the infinitude of primes: a historical survey of its proofs (300 B.C.--2012) and another new proof // arXiv:1202.3670 [math]. — 2012. — 16 лютого. з джерела 12 червня 2018.
5. Saidak, 2006.
6. Pinasco, 2009, с. 172–173.
7. Whang, 2010, с. 181.
8. Debnath, 2010, с. 214.
9. Верещагин, Успенский, Шень, 2013, с. 267.
10. Диамонд Г. Элементарные методы в изучении распределения простых чисел // УМН. — 1990. з джерела 7 липня 2018.

Література

• Начала Евклида / Перевод с греческого и комментарии ^[ru] при редакционном участии ^[ru] и И. Н. Веселовского. — М.—Л. : ГТТИ, 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. — .
• 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. — .
• ^[ru], ^[ru], ^[ru]. Колмогоровская сложность и алгоритмическая случайность. — Издательство Московского центра непрерывного математического образования, 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