Osnovna teorema aritmetike

Osnovna teorema aritmetike ili „teorema o jedinstvenoj faktorizaciji” jeste tvrđenje da svaki prirodan broj veći od 1 je ili prost broj ili se može na jedinstven način predstaviti kao proizvod prostih brojeva, do nivoa redosleda činilaca. Na primer

1200 = 2⁴ × 3¹ × 5² = 3 × 2 × 2 × 2 × 2 × 5 × 5 = 5 × 2 × 3 × 2 × 5 × 2 × 2 = itd.

odnosno, prvo je značajno da se broj 1200 može predstaviti kao proizvod prostih brojeva, i drugo to su uvek isključivo četiri dvojke, jedna trojka i dve petice (eventualno u drugačijem rasporedu).

Svaki prirodan broj $n>1$ je moguće napisati kao $n=p_{1}\cdot \dots \cdot p_{k}$, gde je $p_{1},\dots ,p_{k}$ — prost broj, pri čemu je takva prezentacija tačna do redosleda činilaca.

$\forall n\in \mathbb {N} ,n=p_{1}^{d_{1}}\cdot p_{2}^{d_{2}}\cdot \dots \cdot p_{k}^{d_{k}}=\prod _{i=1}^{k}p_{i}^{d_{i}},$ gde su $p_{1}<p_{2}<\dots <p_{k}$ — prosti brojevi, i $d_{1},\dots ,d_{k}$ — prirodni brojevi.

Važno je primetiti da se broj 1 ne tretira kao prost broj, jer faktorizacija više ne bi bila jednoznačna, kao kod 2 = 2×1 = 2×1×1 = ...

Osnovna teorema

Prosti brojevi, odnosno prim-brojevi su oni koji imaju samo dva tačna delioca: jedinicu i samog sebe. To je slučaj sa 2, 3, 5, 7, 11, 13,17, 19, 23, .... Po konvenciji smatra se da 1 nije prost broj. Prostih brojeva ima beskonačno mnogo, ali što dalje napredujemo u skupu prirodnih brojeva, to ih sve ređe nalazimo: između 1 i 10 imamo 4 prosta broja, što čini 40%; između 1 i 100 ima 25 prostih brojeva, tj. 25%; između 1 i 1000 ima ih 144, dakle 14,4%; ...; između 1 i milijardu (10⁹), ima ih 48 254 942, tj. manje od 4,8%. Upravo oni, prosti brojevi, su i najveća zagonetka aritmetike. U to se možemo uveriti na svakom koraku.

Primer

Prosti brojevi su blizanci ako im je razlika dva (blizanci su 3 i 5, ili 4001 i 4003). Pitanje bez odgovora u današnjoj matematici je: ima li blizanaca beskonačno ili ne?

Ipak, još pre par hiljada godina Euklid je dokazao osnovno pravilo aritmetike: svaki prirodan broj je ili prost broj ili je proizvod prostih brojeva. U savremenoj formulaciji osnovni stav aritmetike glasi: svaki prirodan broj može se predstaviti u obliku proizvoda prostih faktora i njegovo predstavljanje je jedinstveno do poretka faktora. To će biti rečeno još preciznije u teoremi 2, u nizu od tri naredne teoreme.

Faktori

Teorema 1

Ako je n prirodan broj, onda je n proizvod prostih faktora.

Dokaz

Za prost broj n tvrđenje važi očigledno, on je proizvod jedinice i samog sebe. Tvrđenje svakako važi za brojeve n = 1, 2, 3 i možda za još neke. Pretpostavimo da tvrđenje važi za sve složene brojeve manje od n. Ako je i broj n složen broj, tada postoji ceo broj c takav da je 1<c<n, c|n (ovo poslednje čitamo "c deli n", što znači da je broj n deljiv brojem c). Označimo sa m najmanji od pomenutih brojeva c. Takav m ne može biti složen broj, jer bi tada postojao ceo broj k, takav da je 1<k<m, k|m, što bi značilo i k|n. Međutim, to je kontradikcija sa pretpostavkom da je m najmanji prirodan broj koji je delitelj od n. Dakle, broj m je prost broj. Označimo ga sa p₁. Tada mora biti n=p₁n₁, gde je 1<n₁<n. Matematička indukcija će dalje dati da se i broj n₁ može zatim faktorisati. Prema tome, može se faktorisati i polazni broj n. Kraj dokaza.

Primer 1

U samoposluzi se jaja prodaju u pakovanjima od po dvanaest jaja. Svako od tih pakovanja možemo raspakovati u po tri manja paketa sa po četiri jajeta, zato što je broj 12 deljiv sa 3 i sa 4, tako da je 3h4=12.

Primer 2

Da bismo rastavili neki broj na proste činioce postupno ćemo proveravati da li je deljiv sa dva, sa tri, sa pet, i redom sa prostim brojevima. Za to možemo koristiti kriterijume deljivosti. Recimo, 156=2h78=2h2h39=2h2h3h13. Dakle, 2, 2, 3, 13 su prosti brojevi, faktori broja 156.

Kriterijumi deljivosti

broj je deljiv sa 2 ako se završava sa nulom ili parnom cifrom;

deljiv je sa 3, ako je zbir cifara deljiv sa 3;

sa 5 ako se završava nulom ili peticom;

broj je deljiv sa 11 ako je zbir cifara tog broja na neparnim pozicijama oduzet od zbira njegovih cifara na parnim pozicijama jednak nuli ili je deljiv sa 11.

Kanonski oblik

Grupišući jednake proste faktore broja n, onda se prirodan broj može predstaviti u obliku

$n=\prod _{i=1}^{k}p_{i}^{\alpha _{i}},$ gde je $p_{1}<p_{2}<...<p_{k},\;\alpha _{i}>0,\;i=1,2,...,k.$ Takvo predstavljanje nazivamo kanonski oblik broja n.

Teorema 2

Svaki prirodan broj ima jedinstven kanonski oblik.

Dokaz

Na osnovu teoreme 1 kanonsko predstavljanje postoji, a kanonski oblik prostog broja je, očigledno, jedinstven. Za ostale brojeve, dokaz izvodimo svođenjem na kontradikciju. Pretpostavimo da postoji prirodan broj koji se može predstaviti u kanonskom obliku na dva različita načina. Neka je n najmanji takav broj $n=p_{1}p_{2}...p_{k}=q_{1}q_{2}...q_{m}.$ Nijedan od brojeva p ne može se pojaviti u obe kanonske reprezentacije broja n zbog pretpostavke o minimalnosti n. Brojeve je uvek moguće poredati po veličini i recimo $p_{1}\leq p_{2}\leq ...\leq p_{k},\;q_{1}\leq q_{2}\leq ...\leq q_{m}.$ Za proste faktore $p_{1}$ i $q_{1}$ važi $p_{1}\neq q_{1},$ pa možemo uzeti da je $p_{1}<q_{1}.$ Neka je $u=p_{1}q_{2}...q_{m}.$ Iz $p_{1}|u,p_{1}|n$ sledi $p_{1}|(n-u),$ gde je $n-u=(q_{1}-p_{1})q_{2}...q_{m}>1.$ Dakle broj n-u može se napisati u obliku $n-u=p_{1}t_{1}...t_{h},$ gde su $t_{i}$ prosti brojevi, za $i=1,2,...,h.$ Međutim, iz $q_{1}-p_{1}>1$ povlači rastavljanje na proste faktore, na primer $q_{1}-p_{1}=r_{1}r_{2}...r_{s},$ pa sledi drugačiji zapis broja $n-u=r_{1}r_{2}...r_{s}q_{.}..q_{m},$ gde nema prostog faktora $p_{1}.$ To proizilazi iz $p_{1}\neq q_{i},i=1,2,...,m,$ i sa druge strane $p_{1}\neq r_{j},j=1,2,...,s,$ jer $p_{1}$ nije delitelj od $q_{1}-p_{1}.$ Dakle broj n-u ima dve različite faktorizacije, jer samo jedna od njih sadrži prost faktor $p_{1}.$ To važi i u slučaju kada je $q_{1}-p_{1}=1.$ Međutim, $1<n-u<n,$ a to je u kontradikciji sa pretpostavkom o minimalnosti broja n. Dakle, ne postoji ceo broj veći od 1 koji se može na dva načina predstaviti u kanonskom obliku. Kraj dokaza.

To je osnovna teorema aritmetike. Postoji mnogo različitih dokaza ove teoreme i nijedan nije trivijalan, jer se na kraju oslanja na posebnosti skupa prirodnih brojeva u odnosu, recimo na njegove zatvorene podskupove. Na primer, skup parnih brojeva je podskup skupa svih prirodnih brojeva N i takođe je zatvoren na operacije sabiranja i množenja, kao i N. Parni brojevi koji pri deljenju sa 4 daju ostatak 2, to su brojevi oblika 4k+2, nazivaju se parno-prosti. Svaki paran broj može se predstaviti u obliku proizvoda parno-prostih brojeva. Međutim, razlaganje na parno-proste faktore nije uvek jedinstveno. Broj 360 može se faktorisati na parno-proste brojeve na više načina: 2x2x90=2x6x30=2x10=6x6x10.

Reprezentacije

Teorema 3

Neka su brojevi c i n dati u kanonskom obliku

$c=\prod _{i=1}^{k}p_{i}^{\gamma _{i}},\quad n=\prod _{i=1}^{k}p_{i}^{\beta _{i}}.$

Tada je $c|n\,$ ako i samo ako je $0\leq \gamma _{i}\leq \beta _{i},$ za $i=1,2,...,k.\,$

Dokaz

Sledi iz $n=cm,\;m=\prod _{i=1}^{k}p_{i}^{\alpha _{i}},$ gde je $\alpha _{i}=\beta _{i}-\gamma _{i},i=1,2,...,k.\,$ Kraj dokaza.

Vidi još

• Ratko Tošić, mr Vanja Vukosavlavčević, Elementi teorije brojeva, Alef, Novi Sad, 1995.
• Eratostenovo sito
• Rimanova zeta-funkcija

Literatura

• Gauss, Carl Friedrich (1986), Disquisitiones Arithemeticae (Second, corrected edition), Prevod: Clarke, Arthur A., New York: Springer, ISBN 978-0-387-96254-2 
• Gauss, Carl Friedrich (1965), Untersuchungen über hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition) (na jeziku: nemački), Prevod: Maser, H., New York: Chelsea, ISBN 0-8284-0191-8 
• Gauss, Carl Friedrich (1828), Theoria residuorum biquadraticorum, Commentatio prima, Göttingen: Comment. Soc. regiae sci, Göttingen 6 
• Gauss, Carl Friedrich (1832), Theoria residuorum biquadraticorum, Commentatio secunda, Göttingen: Comment. Soc. regiae sci, Göttingen 7 
• Euclid (1956), The thirteen books of the Elements, 2 (Books III-IX), Translated by Thomas Little Heath (Second Edition Unabridged izd.), New York: Dover, ISBN 978-0-486-60089-5 
• Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd izd.), Lexington: D. C. Heath and Company, LCCN 77-171950 .
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 77-81766 
• Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0-8176-3743-5 
• Weil, André (2007) [1984], Number Theory: An Approach through History from Hammurapi to Legendre, Modern Birkhäuser Classics, Boston, MA: Birkhäuser, ISBN 978-0-817-64565-6 
• Goles, E.; Schulz, O.; Markus, M. (2001). „Prime number selection of cycles in a predator-prey model”. Complexity. 6 (4): 33—38. Bibcode:2001Cmplx...6d..33G. doi:10.1002/cplx.1040. 
• Campos, Paulo R.A.; de Oliveira, Viviane M.; Giro, Ronaldo; Galvão, Douglas S. (2004). „Emergence of prime numbers as the result of evolutionary strategy”. Physical Review Letters. 93 (9): 098107. Bibcode:2004PhRvL..93i8107C. PMID 15447148. S2CID 88332. arXiv:q-bio/0406017 . doi:10.1103/PhysRevLett.93.098107. 
• „Invasion of the Brood”. The Economist. 6. 5. 2004. Pristupljeno 2006-11-26. CS1 održavanje: Format datuma (veza)
• Zimmer, Carl (15. 5. 2015). „Bamboo Mathematicians”. Phenomena: The Loom. National Geographic. Arhivirano iz originala 17. 05. 2015. g. Pristupljeno 22. 2. 2018. CS1 održavanje: Format datuma (veza)

Spoljašnje veze

• Why isn’t the fundamental theorem of arithmetic obvious?
• GCD and the Fundamental Theorem of Arithmetic at cut-the-knot.
• PlanetMath: Proof of fundamental theorem of arithmetic
• Fermat's Last Theorem Blog: Unique Factorization, a blog that covers the history of Fermat's Last Theorem from Diophantus of Alexandria to the proof by Andrew Wiles.
• "Fundamental Theorem of Arithmetic" by Hector Zenil, Wolfram Demonstrations Project, 2007.
• Grime, James, „1 and Prime Numbers”, Numberphile, Brady Haran, Arhivirano iz originala 2021-12-11. g.