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 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.

DokazUredi

KonstrukcijaUredi

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 faktoraUredi

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.

PrimjeriUredi

Uzmimo   Tada je   Slično za primjerice   Sada je  

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

IzvoriUredi

  1. Andrej Dujella, Teorija brojeva, Zagreb 2019.

Vanjske povezniceUredi