Osnovni teorem aritmetike
Osnovni teorem aritmetike ili osnovni stavak aritmetike je temeljni teorem u aritmetici i elementarnoj teoriji brojeva.
Teorem tvrdi da se bilo koji prirodni broj [math]\displaystyle{ n \gt 1 }[/math] može prikazati kao umnožak potencija prostih brojeva i to jedinstveno do na poredak faktora, tj. [math]\displaystyle{ n }[/math] se jedinstveno može prikazati kao [math]\displaystyle{ n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_i^{\alpha_i} }[/math] gdje su [math]\displaystyle{ p_1, \ldots, p_i }[/math] međusobno različiti prosti brojevi.[1]
Teorem je prvi dokazao Euklid. Ipak, prvi moderni dokaz teorema je izveo mladi Gauss koristeći modularnu aritmetiku.
Dokaz
Konstrukcija
Neka je [math]\displaystyle{ n }[/math] složeni prirodni broj. Pretpostavimo da se on ne može (u potpunosti) faktorizirati kao u iskazu teorema. Kako [math]\displaystyle{ n }[/math] nije prost slijedi da ima barem dva djelitelja različita od 1 i od [math]\displaystyle{ n }[/math].
Pretpostavimo zato da se [math]\displaystyle{ n }[/math] može prikazati kao [math]\displaystyle{ n = k \cdot l }[/math] gdje je [math]\displaystyle{ k \in \mathbb{N} }[/math] moguće potpuno faktorizirati kao u iskazu, a [math]\displaystyle{ l \in \mathbb{N} }[/math] barem jedan djelitelj broja [math]\displaystyle{ n }[/math] koji se ne može potpuno faktorizirati. Zbog pretpostavke mora vrijediti da je [math]\displaystyle{ l }[/math] složen, tj. [math]\displaystyle{ l }[/math] sadrži barem 2 faktora veća od [math]\displaystyle{ 1 }[/math]: [math]\displaystyle{ l = ab }[/math] za [math]\displaystyle{ a, b \in \{2, 3, ...\}. }[/math] No sada se, slično, [math]\displaystyle{ a }[/math] i [math]\displaystyle{ b }[/math] ne mogu prikazati kao u iskazu pa su složeni, tj. možemo pisati [math]\displaystyle{ l = a_1 \cdot a_2 \cdot b_1 \cdot b_2 }[/math] (vrijedi [math]\displaystyle{ a = a_1a_2 }[/math], [math]\displaystyle{ b = b_1b_2 }[/math]). No, taj proces bismo onda mogli ponoviti za [math]\displaystyle{ a_1 }[/math], [math]\displaystyle{ a_2 }[/math], [math]\displaystyle{ b_1 }[/math] i [math]\displaystyle{ b_2 }[/math]. Prema tome, da pretpostavka vrijedi ovaj algoritam ne bi imao kraja, što znači da bi [math]\displaystyle{ n }[/math] bio beskonačno velik. To je u kontradikciji s činjenicom da je [math]\displaystyle{ n }[/math] prirodan broj. Prema tome u nekom trenutku se mora dogoditi da se neki faktor [math]\displaystyle{ x }[/math] broja [math]\displaystyle{ n }[/math] ne može dodatno rastavljati (osim na trivijalan način, [math]\displaystyle{ x = x \cdot 1 }[/math]), a to je jedino moguće ako je taj posljednji faktor [math]\displaystyle{ x }[/math] u algoritmu prost broj. Naravno neki faktori se mogu i ponavljati. Poredak faktora je proizvoljan zbog komutativnosti množenja. Time smo konstruirali navedeni rastav broja [math]\displaystyle{ n }[/math].
Jedinstvenost do na poredak faktora
Pretpostavimo da je [math]\displaystyle{ n }[/math] najmanji prirodni broj koji se može prikazati na barem dva načina kao umnožak prostih faktora, tj. [math]\displaystyle{ n = p_1p_2\ldots p_i = q_1q_2\ldots q_i. }[/math] Očito [math]\displaystyle{ p_j | q_1q_2\ldots q_i. }[/math] Prema Euklidovoj lemi vrijedi [math]\displaystyle{ p_i | q_j. }[/math] Neka bez smanjenja općenitosti [math]\displaystyle{ p_1 | q_1. }[/math] No, onda se i broj [math]\displaystyle{ p_2\ldots p_j = q_2\ldots q_1 }[/math] može prikazati nejedinstveno, što je u očiglednoj kontradikciji s pretpostavkom o minimalnosti broja [math]\displaystyle{ n. }[/math] Ovime je teorem dokazan.
Primjeri
Uzmimo [math]\displaystyle{ n = 40. }[/math] Tada je [math]\displaystyle{ 40 = 8 \cdot 5 = 2^3 \cdot 5. }[/math] Slično za primjerice [math]\displaystyle{ n = 444. }[/math] Sada je [math]\displaystyle{ 444 = 2^2 \cdot 3 \cdot 37. }[/math]
Naravno, jedinstveni način za prikazati [math]\displaystyle{ 1, p }[/math] kao u iskazu teorema je [math]\displaystyle{ 1 = 1, p = p }[/math] gdje je [math]\displaystyle{ p }[/math] prost broj.
Izvori
- ↑ Andrej Dujella, Teorija brojeva, Zagreb 2019.