Teorema fondamentale dell'aritmetica
Un numero intero n>1 si può fattorizzare nel prodotto di un numero finito k di elementi irriducibili f_k ( numeri primi ) distinti tra loro con esponente positivo e_k>0 e la fattorizzazione è unica. $$ n=f_1^{e_1} \cdot f_2^{e_2} ... f_k^{e_k} $$
La fattorizzazione del numero intero è unica.
Può soltanto cambiare l'ordine degli elementi irriducibili nel prodotto.
Esempio
Il numero 36 è scomposto nei seguenti fattori primi
$$ \begin{array}{c|lcr} n & \text{d} & \\ \hline 36 & 2 \\ 18 & 2 \\ 9 & 3 \\ 3 & 3 \\ 1 \end{array} $$
Quindi posso riscrivere il numero nel seguente modo
$$ 2^2 \cdot 3^2 $$
Sia 2 che 3 sono entrambi irriducibili.
Dimostrazione
Esistenza della fattorizzazione
La fattorizzazione del numero n=2 è molto semplice.
$$ 2 = 2^1 $$
Per induzione ipotizzo di aver provato l'esistenza della fattorizzazione per ogni numero k≥2 e k<n.
Devo dimostrare che la fattorizzazione esista anche per n.
- Se n è irriducibile la fattorizzazione coincide con n
- Se n è riducibile posso scriverlo come fattorizzazione di due numeri interi a e b $$ n = a \cdot b $$ dove a,b sono due interi compresi tra k≥2 e k<n.
- Per ipotesi esiste una fattorizzazione per ogni numero compreso tra k≥2 e k<n. Quindi anche per i numeri a e b.
- Di conseguenza esiste una fattorizzazione anche per il numero n
Ho così dimostrato l'esistenza della fattorizzazione per ogni numero intero n non nullo.
Unicità della fattorizzazione
Sia m il numero dei fattori irriducibili di una fattorizzazione di lunghezza minima.
Se m=1 allora il numero p è irriducibile ( numero primo ).
$$ p = p^1 $$
Per ipotesi assurda suppongo che p abbia anche un'altra fattorizzazione
$$ p = q_1^{k_1} \cdot q_1^{k_2} ... q_n^{k_n} $$
Dove q sono fattori maggiori di 1 e gli esponenti k sono maggiori di zero.
Poiché p divide se stesso allora dividerà anche un fattore qx del membro di destra.
Se p è divisore di qx ed è un numero primo, allora qx è uguale a p.
$$ p|q_x \rightarrow q_x = p $$
Posso riscrivere l'uguaglianza in questo modo
$$ p = q_x \cdot q_1^{k_1} \cdot q_1^{k_2} ... q_n^{k_n} $$
Poiché qx è uguale a p, l'uguaglianza è verificata solo se gli esponenti degli altri fattori sono nulli.
$$ p = q_x \cdot q_1^{0} \cdot q_1^{0} ... q_n^{0} $$
$$ p = q_x \cdot 1 \cdot 1 ... 1 $$
$$ p = q_x $$
$$ p = p $$
Ho così dimostrato che la base dell'induzione.
Ora, per ipotesi l'unicità della fattorizzazione per m-1 fattori irriducibili è provata.
Prendo un intero n con una fattorizzazione in m fattori irriducibili con pi>1 di lunghezza minima uguale a m.
$$ n = p^{h_1} \cdot ... \cdot p^{h_m} $$
per ipotesi n ha anche un'altra fattorizzazione in m fattori irriducibili con qi>1
$$ n = q^{h_1} \cdot ... \cdot q^{h_t} $$
Quindi si ha l'uguaglianza
$$ p^{h_1} \cdot ... \cdot p^{h_s} = q^{h_1} \cdot ... \cdot q^{h_t} $$
Ora,. sia p1 un numero primo che divide un qualche qi al secondo membro
$$ p^{h_1} \cdot ... \cdot p^{h_s} = q^{h_1} \cdot ...\cdot q_i \cdot ... \cdot q^{h_t} $$
posso cancellare sia p1 che qi da ambo i membri dell'ugaglianza.
Adesso il numero dei fattori irriducibili in p è m-1.
Per l'ipotesi iniziale p è una fattorizzazione unica.
Ne consegue che tutti i fattori di qi sono uguali a pi al di là dell'ordine di presentazione.
Ho così dimostrato l'unicità della fattorizzazione di lunghezza minima.
E così via.