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. Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} se jedinstveno može prikazati kao Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot \ldots \cdot p_i^{\alpha_i} } gdje su $p_{1},\ldots ,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, Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x = x \cdot 1 } ), a to je jedino moguće ako je taj posljednji faktor Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } .

Jedinstvenost do na poredak faktora

Pretpostavimo da je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } najmanji prirodni broj koji se može prikazati na barem dva načina kao umnožak prostih faktora, tj. Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = p_1p_2\ldots p_i = q_1q_2\ldots q_i. } Očito Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_j | q_1q_2\ldots q_i. } Prema Euklidovoj lemi vrijedi Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i | q_j. } Neka bez smanjenja općenitosti Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_1 | q_1. } No, onda se i broj Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_2\ldots p_j = q_2\ldots q_1 } može prikazati nejedinstveno, što je u očiglednoj kontradikciji s pretpostavkom o minimalnosti broja Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n. } Ovime je teorem dokazan.

Primjeri

Uzmimo Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 40. } Tada je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 40 = 8 \cdot 5 = 2^3 \cdot 5. } Slično za primjerice Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 444. } Sada je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 444 = 2^2 \cdot 3 \cdot 37. }

Naravno, jedinstveni način za prikazati Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1, p } kao u iskazu teorema je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 = 1, p = p } gdje je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p } prost broj.

Vanjske poveznice

• Osnovni teorem aritmetike u Proleksis enciklopediji