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 \dots \cdot p_i^{{\alpha }_i}$ gdje su $p_1,\dots ,p_i$ međusobno različiti prosti brojevi.

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\dots p_i=q_1{q}_2\dots q_i.$ Očito $p_j|q_1{q}_2\dots 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\dots p_j=q_2\dots q_1$ može prikazati nejedinstveno, što je u očiglednoj kontradikciji s pretpostavkom o minimalnosti broja $n.$ Ovime je teorem dokazan.

Primjeri

Uzmimo $n=40.$ Tada je $40=8\cdot 5=2^3\cdot 5.$ Slično za primjerice $n=444.$ Sada je $444=2^2\cdot 3\cdot 37.$

Naravno, jedinstveni način za prikazati $1,p$ kao u iskazu teorema je $1=1,p=p$ gdje je $p$ prost broj.

Vanjske poveznice

• Osnovni teorem aritmetike u Proleksis enciklopediji