Теорема Евкліда
Теорема Евкліда — фундаментальний елемент теорії чисел. Вона стверджує, що для будь-якого скінченного списку простих чисел знайдеться просте число, яке не увійшло до цього списку (тобто існує безліч простих чисел).
Є кілька відомих доведень цієї теореми.
Найстаріше відоме доведення цього факту навів Евклід у «Началах» (книга IX, твердження 20[1]). При цьому Евклід не використовує поняття нескінченності, а доводить це твердження в такому формулюванні: простих чисел більше, ніж будь-яка вибрана їх множина.
Евклід доводить це так.
Припустимо, що дано деякий скінченний список простих чисел . Евклід доводить, що існує просте число, яке не входить до цього списку.
Нехай — найменше спільне кратне цих чисел, .
Евклід розглядає число . Якщо — просте, то знайдено просте число, яке не входить до цього списку (оскільки воно більше від кожного числа зі списку).
Якщо ж не є простим, то існує деяке просте число , на яке число ділиться націло. Але не може бути одночасно і дільником , і елементом списку оскільки тоді при діленні на була б остача, не рівна нулю. Отже, існує просте число , яке не входить до жодного (скінченного) списку простих чисел .
Часто при викладі доведення теореми Евкліда починають із розгляду одразу множини всіх простих чисел (у припущенні, що ця множина містить скінченну кількість елементів), і далі ведуть доведення теореми від супротивного. Хоча таке доведення також можливе, оригінальне міркування Евклід проводить елегантніше — саме для будь-якого скінченного набору простих чисел, і доводить, що має існувати якесь просте число, яке не входить до цього (будь-якого) набору простих чисел[2].
Коротка форма доведення Евкліда:
![]() |
Нехай дано скінченний набір простих чисел. Покажемо, що існує просте число, яке не входить до цього набору. Перемножимо числа з цього набору та додамо одиницю. Отримане число не ділиться на жодне число з цього набору, тому що остача від ділення на будь-яке з них дає одиницю. Значить, число має ділитися на просте число, не включене в цей набір. | ![]() |
Інші варіації доведення Евкліда використовують факторіал: n! ділиться на будь-яке ціле від 2 до n, оскільки він є їх добутком. Отже, n! + 1 не ділиться на жодне натуральне число від 2 до n включно (при діленні на будь-яке з цих чисел отримаємо остачу 1). Отже, n! + 1 або є простим, або ділиться на просте число, більше ніж n. У будь-якому випадку ми маємо для будь-якого натурального числа n щонайменше одне просте число, більше від n . Звідси робимо висновок, що простих чисел нескінченно багато[3].
Деякі пов'язані доведення цієї теореми використовують так звані евклідові числа (послідовність A006862 з Онлайн енциклопедії послідовностей цілих чисел, OEIS): , де — добуток перших простих чисел (прайморіал). При цьому, формально кажучи, доведення, яке навів Евклід, не використовує цих чисел. Як сказано вище, Евклід показує, що для будь-якого скінченного набору простих чисел (не обов'язково перших простих чисел) існує просте число, яке не включене в цей набір[4].
Інше доведення, як е запропонував Леонард Ейлер, спирається на основну теорему арифметики, яка стверджує, що будь-яке ціле число має єдиний розклад на прості множники. Якщо позначити через P множину всіх простих чисел, можна записати рівність:
Перша рівність виходить із формули для геометричного ряду в кожному множнику добутку. Друга рівність виходить перестановкою місцями добутку та суми:
У результаті будь-який добуток простих чисел з'являється у формулі лише один раз, а тоді, відповідно до основної теореми арифметики, сума дорівнює сумі за всіма натуральними числами[a].
Сума справа є розбіжним гармонічним рядом, так що добуток зліва повинен також бути розбіжним, що неможливо, якщо кількість елементів у множині P скінченна.
З цього доведення Ейлер отримав сильніше твердження, ніж теорема Евкліда, а саме розбіжність суми обернених значень простих чисел.
Пал Ердеш надав третє доведення, яке також спирається на основну теорему арифметики. Спочатку звернемо увагу на те, що будь-яке натуральне число n можна подати у вигляді
- ,
де є вільним від квадратів (не ділиться на жоден повний квадрат). Ми можемо взяти як найбільший квадрат, який ділить , а тоді . Тепер припустимо, що є лише скінченна кількість простих чисел та позначимо цю кількість простих чисел буквою . Оскільки кожне просте число може з'явитися в розкладі будь-якого вільного від квадратів числа лише раз, згідно з основною теоремою арифметики, є тільки вільних від квадратів чисел.
Тепер зафіксуємо деяке натуральне число і розглянемо натуральні числа між 1 та . Кожне з цих чисел можна записати у вигляді де — вільне від квадратів число, а є квадратом:
- (1·1, 2·1, 3·1, 1·4, 5·1, 6·1, 7·1, 2·4, 1·9, 10·1, …)
У списку різних чисел і кожне з них є добутком вільного від квадратів числа на квадрат, що не перевищує . Є таких квадратів. Тепер утворюємо всі можливі добутки всіх квадратів, що не перевищують , на всі вільні від квадратів числа. Є рівно таких чисел, всі вони різні і включають усі числа з нашого списку, а можливо, й більше. Отже, . Тут означає цілу частину.
Оскільки нерівність не виконується для досить великого , простих чисел має бути нескінченно багато.
1955 року Гілель Фюрстенберг[en] опублікував нове доведення нескінченності кількості простих чисел, використовуючи топологію точкових множин[en].
2006 року Філіп Сайдак надав таке конструктивне доведення, яке не використовує доведення до абсурду[5] або лему Евкліда (про те, що, якщо просте число p ділить ab, воно має ділити або a, або b).
Оскільки кожне натуральне число () має щонайменше один простий множник, а два послідовні числа і не мають спільного дільника, добуток і має більше різних простих дільників, ніж саме число . Таким чином, ланцюжок прямокутних чисел: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].
Нехай — найменші простих чисел. Тоді, згідно з принципом включень-виключень, кількість додатних цілих чисел, що не перевищують і діляться на ці прості числа, дорівнює
Поділивши на і спрямувавши , маємо
Це можна переписати як
Якщо ніяких інших простих чисел, відмінних від , не існує, вираз у (1) дорівнює і вираз (2) дорівнює 1, проте ясно, що вираз (3) одиниці не дорівнює. Таким чином, повинні існувати прості числа, відмінні від .
2010 року Джун Хо Пітер Ванг опублікував таке доведення від супротивного[7]. Нехай k — деяке натуральне число. Тоді, згідно з формулою Лежандра[en]
- (добуток за всіма простими числами)
де
Але якщо існує тільки скінченна кількість простих чисел,
(чисельник дробу зростає експонентно, тоді як у формулі Стірлінґа знаменник зростає швидше від простої експоненти), що суперечить тому, що для кожного чисельник більший або дорівнює знаменнику.
Подання формули Лейбніца для у вигляді добутку Ейлера[en] дає[8]
Чисельниками є непарні прості числа, а кожен знаменник є найближчим до чисельника числом, кратним 4.
Якби простих чисел була скінченна кількість, ця формула дала б для раціональне подання, знаменник якого є добутком усіх чисел, що суперечить ірраціональності .
Олександр Шень[ru] та інші надали доведення з використанням метод нестисливості[en][9] та колмогоровську складність: Припустимо, що є тільки простих чисел (). Відповідно до основної теореми арифметики, будь-яке натуральне число подаване у вигляді
де невід'ємні цілі числа разом зі списком скінченного розміру простих чисел достатні для реконструкції числа. Оскільки для всіх , звідси випливає, що всі (де означає логарифм за основою 2).
Це дає метод кодування для такого розміру (використовуючи нотацію «O велике»):
- біт.
Це значно ефективніше кодування, ніж подання безпосередньо в двійковому коді, яке вимагає біт. Установлений результат про стиснення без втрат стверджує, що немає алгоритму стиснення без втрат біт інформації у менш ніж біт. Наведене вище подання порушує це твердження, оскільки за досить великих .
Отже, простих чисел нескінченно багато.
Теорема про розподіл простих чисел стверджує, що кількість простих чисел менших від , що позначається як , зростає як [10].
- ↑ Ця рівність є окремим випадком формули для добутку Ейлера[en] для дзета-функції Рімана[en].
- ↑ Начала Евклида та 1949—1951, с. 89, Книга IX, Предложение 20.
- ↑ Hardy, Michael; Woodgold, Catherine. Prime Simplicity // The Mathematical Intelligencer. — 2009. — Vol. 31, no. 4. — P. 44—52. — DOI: .(англ.)
- ↑ Bostock, Chandler, Rourke, 2014, с. 168.
- ↑ 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.
- ↑ Saidak, 2006.
- ↑ Pinasco, 2009, с. 172–173.
- ↑ Whang, 2010, с. 181.
- ↑ Debnath, 2010, с. 214.
- ↑ Верещагин, Успенский, Шень, 2013, с. 267.
- ↑ Диамонд Г. Элементарные методы в изучении распределения простых чисел // УМН. — 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. — 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: .
- Lokenath Debnath. The Legacy of Leonhard Euler: A Tricentennial Tribute. — World Scientific, 2010. — С. 214. — ISBN 9781848165267.
- Верещагин Н. К.[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