Osnovni teorem aritmetike: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
Stvorena nova stranica sa sadržajem: »'''Osnovni stavak aritmetike''' ili '''Fundamentalni teorem aritmetike''' je temeljni teorem u aritmetici i Teorija brojeva|elementarno...«. Oznake: mobilni uređaj m.wiki |
Oznake: mobilni uređaj m.wiki |
||
Redak 4:
== Dokaz ==
=== 1. Konstrukcija ===
Neka imamo neki prirodni složeni broj <math> n. </math> Pretpostavimo da se on ne može (u potpunosti) faktorizirati kao u iskazu teorema. Kako <math> n </math> nije prost slijedi da <math> n </math> ima barem dva djelitelja različita od <math> 1 </math> 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, a, b \in \{2, 3, ...\}. </math> No sada se, slično, oba <math> a, 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, b = b_1b_2 </math>). No, taj proces bismo onda mogli ponoviti za svaki od <math> a_1, a_2, b_1, 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 apsurdno 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 očit zbog komutativnosti množenja.
=== 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...p_i = q_1q_2...qi. </math> Očito <math> pj | q_1q_2...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...p_j = q_2...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 ==
| |||