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 $n>1$ može prikazati kao umnožak potencija prostih brojeva i to jedinstveno do na poredak faktora, tj. $n$ se jedinstveno može prikazati kao $n=p_{1}^{\alpha _{1}}\cdot p_{2}^{\alpha _{2}}\cdot \ldots \cdot p_{i}^{\alpha _{i}}$ gdje su $p_{1},\ldots ,p_{i}$ 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 $n$ složeni prirodni broj. Pretpostavimo da se on ne može (u potpunosti) faktorizirati kao u iskazu teorema. Kako $n$ nije prost slijedi da ima barem dva djelitelja različita od 1 i od $n$ .

Pretpostavimo zato da se $n$ može prikazati kao $n=k\cdot l$ gdje je $k\in \mathbb {N}$ moguće potpuno faktorizirati kao u iskazu, a $l\in \mathbb {N}$ barem jedan djelitelj broja $n$ koji se ne može potpuno faktorizirati. Zbog pretpostavke mora vrijediti da je $l$ složen, tj. $l$ sadrži barem 2 faktora veća od $1$ : $l=ab$ za $a,b\in \{2,3,...\}.$ No sada se, slično, $a$ i $b$ ne mogu prikazati kao u iskazu pa su složeni, tj. možemo pisati $l=a_{1}\cdot a_{2}\cdot b_{1}\cdot b_{2}$ (vrijedi $a=a_{1}a_{2}$ , $b=b_{1}b_{2}$ ). No, taj proces bismo onda mogli ponoviti za $a_{1}$ , $a_{2}$ , $b_{1}$ i $b_{2}$ . Prema tome, da pretpostavka vrijedi ovaj algoritam ne bi imao kraja, što znači da bi $n$ bio beskonačno velik. To je u kontradikciji s činjenicom da je $n$ prirodan broj. Prema tome u nekom trenutku se mora dogoditi da se neki faktor $x$ broja $n$ ne može dodatno rastavljati (osim na trivijalan način, $x=x\cdot 1$ ), a to je jedino moguće ako je taj posljednji faktor $x$ 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 $n$ .

Jedinstvenost do na poredak faktora

Pretpostavimo da je $n$ najmanji prirodni broj koji se može prikazati na barem dva načina kao umnožak prostih faktora, tj. $n=p_{1}p_{2}\ldots p_{i}=q_{1}q_{2}\ldots q_{i}.$ Očito $p_{j}|q_{1}q_{2}\ldots q_{i}.$ Prema Euklidovoj lemi vrijedi $p_{i}|q_{j}.$ Neka bez smanjenja općenitosti $p_{1}|q_{1}.$ No, onda se i broj $p_{2}\ldots p_{j}=q_{2}\ldots q_{1}$ može prikazati nejedinstveno, što je u očiglednoj kontradikciji s pretpostavkom o minimalnosti broja $n.$ Ovime je teorem dokazan.