Vidi kôd stranice Osnovni teorem aritmetike

'''Osnovni teorem aritmetike''' ili '''osnovni stavak aritmetike''' je temeljni [[teorem]] u [[Aritmetika|aritmetici]] i [[Teorija brojeva|elementarnoj teoriji brojeva]]. 

Teorem tvrdi da se bilo koji prirodni broj <math>n > 1</math> može prikazati kao umnožak [[potencija]] prostih brojeva i to jedinstveno do na poredak faktora, tj. <math>n</math> se jedinstveno može prikazati kao <math>n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_i^{\alpha_i} </math> gdje su <math>p_1, \ldots, p_i</math> međusobno različiti [[prosti broj]]evi.<ref>Andrej Dujella, Teorija brojeva, Zagreb 2019.</ref>

Teorem je prvi dokazao [[Euklid]]. Ipak, prvi moderni dokaz teorema je izveo mladi [[Carl Friedrich Gauss|Gauss]] koristeći [[Modularna aritmetika|modularnu aritmetiku]].

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

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

=== Jedinstvenost do na poredak faktora ===
Pretpostavimo da je <math> n </math> najmanji prirodni broj koji se može prikazati na barem dva načina kao umnožak prostih faktora, tj. <math> n = p_1p_2\ldots p_i = q_1q_2\ldots q_i. </math> Očito <math> p_j | q_1q_2\ldots q_i. </math> Prema ''Euklidovoj lemi'' vrijedi <math> p_i | q_j. </math> Neka bez smanjenja općenitosti <math> p_1 | q_1. </math> No, onda se i broj <math> 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> n. </math> Ovime je teorem dokazan.

== Primjeri ==
Uzmimo <math> n = 40. </math> Tada je <math> 40 = 8 \cdot 5 = 2^3 \cdot 5. </math> 
Slično za primjerice <math> n = 444. </math> Sada je <math> 444 = 2^2 \cdot 3 \cdot 37. </math>

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

==Izvori==
{{izvori}}

== Vanjske poveznice ==
* [https://proleksis.lzmk.hr/2193/ Osnovni teorem aritmetike] u [[Proleksis enciklopedija|Proleksis enciklopediji]]

[[Kategorija:Aritmetika]]
[[Kategorija:Matematički poučci]]