Osnovni teorem aritmetike

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje

Osnovni teorem aritmetike ili osnovni stavak aritmetike je temeljni teorem u aritmetici i elementarnoj teoriji brojeva.

Teorem tvrdi da se bilo koji prirodni broj može prikazati kao umnožak potencija prostih brojeva i to jedinstveno do na poredak faktora, tj. se jedinstveno može prikazati kao gdje su 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[uredi | uredi kôd]

Konstrukcija[uredi | uredi kôd]

Neka je složeni prirodni broj. Pretpostavimo da se on ne može (u potpunosti) faktorizirati kao u iskazu teorema. Kako nije prost slijedi da ima barem dva djelitelja različita od 1 i od .

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

Jedinstvenost do na poredak faktora[uredi | uredi kôd]

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

Primjeri[uredi | uredi kôd]

Uzmimo Tada je Slično za primjerice Sada je

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

Izvori[uredi | uredi kôd]

  1. Andrej Dujella, Teorija brojeva, Zagreb 2019.

Vanjske poveznice[uredi | uredi kôd]