Еуклидова теорема

Еуклидова теорема представља фундаментални исказ у теорији бројева, који тврди да постоји бесконачно простих бројева. Постоји више познатих доказа ове теореме.

Еуклидов доказ

Еуклид је изнео доказ у свом делу Елементи (књига IX, став 20),^[1] који је парафразиран овде.^[2]

Нека је дат било који коначни скуп природних бројева p₁, p₂, ..., p_n. Биће показано да постоји барем још један прост број који се не налази у листи. Нека је P производ свих простих бројева у скупу: P = p₁p₂...p_n. Нека је q = P 1. Тада q или јесте или није прост број:

Ако је q прост, онда постоји бар један број (q) који је прост, а није у првобитном скупу.
Ако q није прост, онда неки прост број p дели q. Кад би овај број p био у скупу, тада би он делио P (јер је P производ свих бројева у скупу); али p дели P 1 = q. Ако p дели P и q, онда би p морао да дели разлику^[3] ова два броја, што је (P 1) − P или једноставно 1. Како ниједан прост број не дели 1, p не може бити у скупу. Ово значи да барем још један прост број мора постојати мимо оних који су већ у скупу.

Ово доказује да за сваки коначни скуп простих бројева постоји прост број који није у том скупу, и стога простих бројева мора бити бесконачно много.

Често се погрешно наводи да је Еуклид доказао своју тврдњу свођењем на контрадикцију, кренувши од претпоставке да почетни скуп садржи све просте бројеве, или да садржи тачно n најмањих простих бројева, уместо произвољног коначног скупа простих бројева.^[4] Уместо свођења на контрадикцију, Еуклидов доказ показује да сваки коначни скуп има наведено својство. Контрадикција не следи из овога, али ниједан од елемената скупа не може да има својство да је делилац броја 1.

Постоји неколико варијација Еуклидовог доказа, укључујући и следећу:

Факторијел n! позитивног целог броја n је дељив сваким целим бројем од 2 до n, јер је производ свих ових бројева. Стога, n! 1 није дељив ни једним од целих бројева од 2 до n, укључујући n (даје остатак 1 кад се подели било којим од њих). Стога, n! 1 је или прост број, или је дељив простим бројем већим од n. У оба случаја, за сваки позитивни цео број n, постоји најмање један прост број већи од n. Закључак је да је простих бројева има бесконачно много.^[5]

Ојлеров доказ

Други доказ, који је осмислио швајцарски математичар Леонард Ојлер, се ослања на основну теорему аритметике: да се сваки цео број може на јединствен начин представити као производ простих бројева. Ако је P скуп свих простих бројева, Ојлер тврди да:

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

Прва једнакост следи из формуле за геометријски ред у сваком терму производа. Друга једнакост је посебан случај формуле Ојлеровог производа за Риманову зета-функцију. Да би се ово показало, потребно је дистрибуирати производ по збиру:

{\begin{aligned}\prod _{p\in P}\sum _{k\geq 0}{\frac {1}{p^{k}}}&=\sum _{k\geq 0}{\frac {1}{2^{k}}}\times \sum _{k\geq 0}{\frac {1}{3^{k}}}\times \sum _{k\geq 0}{\frac {1}{5^{k}}}\times \sum _{k\geq 0}{\frac {1}{7^{k}}}\times \cdots \\[8pt]&=\sum _{k,\ell ,m,n,\cdots \geq 0}{\frac {1}{2^{k}3^{\ell }5^{m}7^{n}\cdots }}=\sum _{n}{\frac {1}{n}}\end{aligned}}

у резултату, сваки производ целих бројева се појављује тачно једном, па је по основној теореми аритметике збир једнак збиру над свим целим бројевима.

Сума са десне стране је хармонијски ред, који дивергира. Стога производ са леве стране мора такође да дивергира. Како је сваки терм у производу коначан, број термова мора бити бесконачан; стога простих бројева мора постојати бесконачно много.

Види још

Теорема о простим бројевима

Напомене и референце

^ James Williamson (превод и коментар), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, стр 63.
^ Прецизна формулација Еуклидове тврдње гласи: „Прости бројеви су бројнији од било ког предложеног мноштва простих бројева“. У доказу из претпоставке да постоји барем три проста броја, Еуклид дедукује постојање четвртог.
^ У општем случају, за свака три цела броја a, b, c ако $a\mid b$ и $a\mid c$ , онда $a\mid (b-c)$ .
^ Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, том 31, број 4, јесен 2009, стране 44–52.
^ Bostock, Linda; Chandler, Suzanne; Rourke, C. (1. 11. 2014). Further Pure Mathematics (на језику: енглески). Nelson Thornes. стр. 168. ISBN 9780859501033.

Додатна литература

Meštrović, Romeo (2012). „Euclid's theorem on the infinitude of primes: A historical survey of its proofs (300 B.C.--2022) and another new proof”. arXiv:1202.3670 .

Спољашње везе

[1] James Williamson (превод и коментар), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, стр 63.

[2] Прецизна формулација Еуклидове тврдње гласи: „Прости бројеви су бројнији од било ког предложеног мноштва простих бројева“. У доказу из претпоставке да постоји барем три проста броја, Еуклид дедукује постојање четвртог.

[3] У општем случају, за свака три цела броја a, b, c ако $a\mid b$ и $a\mid c$ , онда $a\mid (b-c)$ .

[4] Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, том 31, број 4, јесен 2009, стране 44–52.

[5] Bostock, Linda; Chandler, Suzanne; Rourke, C. (1. 11. 2014). Further Pure Mathematics (на језику: енглески). Nelson Thornes. стр. 168. ISBN 9780859501033.

[1]

[2]

[3]

[4]

[5]