Euklidova teorema

Euklidova teorema predstavlja fundamentalni iskaz u teoriji brojeva, koji tvrdi da postoji beskonačno prostih brojeva. Postoji više poznatih dokaza ove teoreme.

Euklidov dokaz[uredi | uredi izvor]

Euklid je izneo dokaz u svom delu Elementi (knjiga IX, stav 20),^[1] koji je parafraziran ovde.^[2]

Neka je dat bilo koji konačni skup prirodnih brojeva p₁, p₂, ..., p_n. Biće pokazano da postoji barem još jedan prost broj koji se ne nalazi u listi. Neka je P proizvod svih prostih brojeva u skupu: P = p₁p₂...p_n. Neka je q = P + 1. Tada q ili jeste ili nije prost broj:

Ako je q prost, onda postoji bar jedan broj (q) koji je prost, a nije u prvobitnom skupu.
Ako q nije prost, onda neki prost broj p deli q. Kad bi ovaj broj p bio u skupu, tada bi on delio P (jer je P proizvod svih brojeva u skupu); ali p deli P + 1 = q. Ako p deli P i q, onda bi p morao da deli razliku^[3] ova dva broja, što je (P + 1) − P ili jednostavno 1. Kako nijedan prost broj ne deli 1, p ne može biti u skupu. Ovo znači da barem još jedan prost broj mora postojati mimo onih koji su već u skupu.

Ovo dokazuje da za svaki konačni skup prostih brojeva postoji prost broj koji nije u tom skupu, i stoga prostih brojeva mora biti beskonačno mnogo.

Često se pogrešno navodi da je Euklid dokazao svoju tvrdnju svođenjem na kontradikciju, krenuvši od pretpostavke da početni skup sadrži sve proste brojeve, ili da sadrži tačno n najmanjih prostih brojeva, umesto proizvoljnog konačnog skupa prostih brojeva.^[4] Umesto svođenja na kontradikciju, Euklidov dokaz pokazuje da svaki konačni skup ima navedeno svojstvo. Kontradikcija ne sledi iz ovoga, ali nijedan od elemenata skupa ne može da ima svojstvo da je delilac broja 1.

Postoji nekoliko varijacija Euklidovog dokaza, uključujući i sledeću:

Faktorijel n! pozitivnog celog broja n je deljiv svakim celim brojem od 2 do n, jer je proizvod svih ovih brojeva. Stoga, n! + 1 nije deljiv ni jednim od celih brojeva od 2 do n, uključujući n (daje ostatak 1 kad se podeli bilo kojim od njih). Stoga, n! + 1 je ili prost broj, ili je deljiv prostim brojem većim od n. U oba slučaja, za svaki pozitivni ceo broj n, postoji najmanje jedan prost broj veći od n. Zaključak je da je prostih brojeva ima beskonačno mnogo.^[5]

Ojlerov dokaz[uredi | uredi izvor]

Drugi dokaz, koji je osmislio švajcarski matematičar Leonard Ojler, se oslanja na osnovnu teoremu aritmetike: da se svaki ceo broj može na jedinstven način predstaviti kao proizvod prostih brojeva. Ako je P skup svih prostih brojeva, Ojler tvrdi da:

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

Prva jednakost sledi iz formule za geometrijski red u svakom termu proizvoda. Druga jednakost je poseban slučaj formule Ojlerovog proizvoda za Rimanovu zeta-funkciju. Da bi se ovo pokazalo, potrebno je distribuirati proizvod po zbiru:

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

u rezultatu, svaki proizvod celih brojeva se pojavljuje tačno jednom, pa je po osnovnoj teoremi aritmetike zbir jednak zbiru nad svim celim brojevima.

Suma sa desne strane je harmonijski red, koji divergira. Stoga proizvod sa leve strane mora takođe da divergira. Kako je svaki term u proizvodu konačan, broj termova mora biti beskonačan; stoga prostih brojeva mora postojati beskonačno mnogo.

Vidi još[uredi | uredi izvor]

Teorema o prostim brojevima

Napomene i reference[uredi | uredi izvor]

^ James Williamson (prevod i komentar), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, str 63.
^ Precizna formulacija Euklidove tvrdnje glasi: „Prosti brojevi su brojniji od bilo kog predloženog mnoštva prostih brojeva“. U dokazu iz pretpostavke da postoji barem tri prosta broja, Euklid dedukuje postojanje četvrtog.
^ U opštem slučaju, za svaka tri cela broja a, b, c ako $a\mid b$ i $a\mid c$ , onda $a\mid (b-c)$ .
^ Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, tom 31, broj 4, jesen 2009, strane 44–52.
^ Bostock, Linda; Chandler, Suzanne; Rourke, C. (1. 11. 2014). Further Pure Mathematics (na jeziku: engleski). Nelson Thornes. str. 168. ISBN 9780859501033.

Dodatna literatura[uredi | uredi izvor]

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 .

Spoljašnje veze[uredi | uredi izvor]

[1] James Williamson (prevod i komentar), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, str 63.

[2] Precizna formulacija Euklidove tvrdnje glasi: „Prosti brojevi su brojniji od bilo kog predloženog mnoštva prostih brojeva“. U dokazu iz pretpostavke da postoji barem tri prosta broja, Euklid dedukuje postojanje četvrtog.

[3] U opštem slučaju, za svaka tri cela broja a, b, c ako $a\mid b$ i $a\mid c$ , onda $a\mid (b-c)$ .

[4] Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, tom 31, broj 4, jesen 2009, strane 44–52.

[5] Bostock, Linda; Chandler, Suzanne; Rourke, C. (1. 11. 2014). Further Pure Mathematics (na jeziku: engleski). Nelson Thornes. str. 168. ISBN 9780859501033.

[1]

[2]

[3]

[4]

[5]