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

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

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

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

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

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

Припустимо, що дано деякий скінченний список простих чисел $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, оскільки він є їх добутком. Отже, Шаблон:Nobr не ділиться на жодне натуральне число від 2 до n включно (при діленні на будь-яке з цих чисел отримаємо остачу 1). Отже, Шаблон:Nobr або є простим, або ділиться на просте число, більше ніж n. У будь-якому випадку ми маємо для будь-якого натурального числа n щонайменше одне просте число, більше від n . Звідси робимо висновок, що простих чисел нескінченно багатоШаблон:Sfn.

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

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

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

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

$\prod _{p\in P}\frac{1}{1-1/p}=\prod _{p\in P}\sum _{k⩾0}\frac{1}{p^k}=\sum _n\frac{1}{n}.$

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

$\begin{array}{cc}\prod _{p\in P}\sum _{k⩾0}\frac{1}{p^k}& =\sum _{k⩾0}\frac{1}{2^k}\cdot \sum _{k⩾0}\frac{1}{3^k}\cdot \sum _{k⩾0}\frac{1}{5^k}\cdot \sum _{k⩾0}\frac{1}{7^k}\cdots \\ & =\sum _{k,\ell ,m,n,\cdots ⩾0}\frac{1}{2^k{3}^{\ell }{5}^m{7}^n\cdots }=\sum _n\frac{1}{n}\end{array}$

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

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

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

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

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

$r{s}^2$ ,

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

Тепер зафіксуємо деяке натуральне число $N$ і розглянемо натуральні числа між 1 та $N$. Кожне з цих чисел можна записати у вигляді $r{s}^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 ⩾N$. Тут $\lfloor x\rfloor$ означає цілу частину.

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

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

1955 року Шаблон:Нп опублікував нове доведення нескінченності кількості простих чисел, використовуючи Шаблон:Не перекладено.

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

Сайдак

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

Нехай $p_1,\dots ;p_N$ — найменші $N$ простих чисел. Тоді, згідно з принципом включень-виключень, кількість додатних цілих чисел, що не перевищують $x$ і діляться на ці прості числа, дорівнює

$\begin{array}{cc}1+\sum _i\lfloor \frac{x}{p_i}\rfloor -\sum _{i<j}\lfloor \frac{x}{p_i{p}_j}\rfloor & +\sum _{i<j<k}\lfloor \frac{x}{p_i{p}_j{p}_k}\rfloor -\cdots \\ & \cdots \pm (-1{)}^{N+1}\lfloor \frac{x}{p_1\cdots p_N}\rfloor .(1)\end{array}$

Поділивши на $x$ і спрямувавши $x\to \mathrm{\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}.(2)$

Це можна переписати як

$1-\prod _{i=1}^N(1-\frac{1}{p_i}).(3)$

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

Ванг

2010 року Джун Хо Пітер Ванг опублікував таке доведення від супротивногоШаблон:Sfn. Нехай k — деяке натуральне число. Тоді, згідно з Шаблон:Не перекладено

$k!=\prod _{p\text{ prime}}{p}^{f(p,k)}$ (добуток за всіма простими числами)

де

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

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

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

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

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

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

Подання формули Лейбніца для $\pi$ у вигляді Шаблон:Не перекладено даєШаблон:Sfn

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

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

Шаблон:Нп та інші надали доведення з використанням Шаблон:Не перекладеноШаблон:Sfn та колмогоровську складність: Припустимо, що є тільки $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⩾2$ для всіх $i$, звідси випливає, що всі $e_i⩽\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)$.

Див. також

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

Література

• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття

Посилання

• Шаблон: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