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 q_x del membro di destra.

Se p è divisore di q_x ed è un numero primo, allora q_x è 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é q_x è 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 p_i>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 q_i>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 p₁ un numero primo che divide un qualche q_i 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 p₁ che q_i 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 q_i sono uguali a p_i al di là dell'ordine di presentazione.

Ho così dimostrato l'unicità della fattorizzazione di lunghezza minima.

E così via.