# Teorema fondamentale dell'aritmetica

Il teorema fondamentale dell'aritmetica afferma che:
    Ogni numero naturale maggiore di 1 o è un numero primo o si può esprimere come prodotto di numeri primi. Tale rappresentazione è unica, se si prescinde dall'ordine in cui compaiono i fattori.
L'enunciato è facilmente verificabile per numeri naturali "piccoli": è facile scoprire che $70$ è pari a $2\times 5\times 7$ e $100$ equivale a $2\times 2\times 5\times 5$ ovvero $2^{2}\times 5^{2}$, ed è altrettanto facile verificare che per questi numeri non possono esistere altre scomposizioni in fattori primi.
Il teorema fu dimostrato per la prima volta, in un linguaggio matematico moderno, da Gauss nelle Disquisitiones Arithmeticae; Euclide, negli Elementi, insieme all'esistenza della fattorizzazione, aveva dimostrato una proposizione, oggi nota come lemma di Euclide, dalla quale si ricava la proprietà di fattorizzazione unica.
Nella teoria degli anelli, un analogo della proprietà espressa dal teorema costituisce la definizione stessa di anello a fattorizzazione unica.

## Dimostrazione del teorema

L'enunciato del teorema asserisce l'esistenza di una fattorizzazione in numeri primi per ogni numero naturale, e successivamente la sua unicità. Dimostriamo separatamente le due affermazioni.

### Dimostrazione dell'esistenza

Dalla definizione di numero primo si deduce che ogni numero maggiore o uguale a 2 o è un numero primo oppure si può esprimere come prodotto di numeri primi. Questo fatto si può dimostrare per induzione:
* n=2 è primo, quindi soddisfa quanto enunciato.
* Supponendo vero l'enunciato per tutti i numeri da 2 a n, dimostriamo che vale anche per n+1. Per n+1 ci sono due possibilità: o è primo oppure è divisibile per un numero a compreso tra 2 e n. Nel caso in cui n+1 sia divisibile per a per l'ipotesi induttiva o a è primo oppure a ha un divisore primo p. In quest'ultimo caso (per la proprietà transitiva della divisibilità) p è anche un divisore di n+1. In ogni caso dunque o n+1 è primo o è divisibile per un primo.
La dimostrazione dell'esistenza della fattorizzazione per ogni numero procede ancora per induzione:
* n=2 è primo e dunque è già banalmente fattorizzato.
* Supponiamo vera l'esistenza di una fattorizzazione per tutti i naturali compresi tra 2 e n e dimostriamola vera anche per n+1. Considerando n+1, abbiamo due casi: n+1 è primo (e quindi è già fattorizzato) oppure n+1 è divisibile per un primo p (come dimostrato nella prima parte); in quest'ultimo caso il numero m=(n+1)/p è minore di n+1, e quindi verifica l'ipotesi induttiva, ovvero esiste una fattorizzazione di m. Ma allora n+1=mp cioè n+1 è fattorizzabile (è il prodotto di m e p).
Quindi l'esistenza di una fattorizzazione è dimostrata per ogni numero naturale n.

### Dimostrazione dell'unicità

Dimostriamo che se un numero ammette una fattorizzazione in numeri primi questa è unica.
Per assurdo: Si supponga che esistano dei numeri scomponibili in fattori primi in più di un modo, e si chiami m il più piccolo (che esiste per il principio del buon ordinamento). Innanzitutto si dimostra che, date due fattorizzazioni di m, i numeri primi che si presentano nella prima fattorizzazione sono tutti distinti da quelli della seconda fattorizzazione. Siano infatti [1] e [2] le due diverse fattorizzazioni di m
    $\left[1\right]\quad m=p_{1}p_{2}p_{3}\dots p_{s}$
    $\left[2\right]\quad m=q_{1}q_{2}q_{3}\dots q_{t}$
dove i $p_{i}$ e i $q_{j}$ sono primi ma differenti tra loro, ovvero $\forall i,j\;\;p_{i}\neq q_{j}$ (se ci fosse un fattore identico $p_{h}=q_{k}$ possiamo ricondurci al caso indicato dividendo $m$ per tale fattore e ottenendo un numero $m'$ a scomposizione multipla per cui vale $m'<m$, contraddicendo l'ipotesi che $m$ sia il più piccolo tra i numeri a scomposizione multipla). All'interno di ogni fattorizzazione ci possono comunque essere fattori ripetuti: ad esempio, 100 = 2×2×5×5.
A questo punto sappiamo che $p_{1}$ è diverso da $q_{1}$; senza perdita di generalità possiamo supporre che $p_{1}<q_{1}$. Poniamo allora
    $\left[3\right]\quad n=(q_{1}-p_{1})q_{2}q_{3}\dots q_{t}$
Evidentemente, $n<m$, dato che la $\left[3\right]$ si può scrivere come
    $\left[4\right]\quad n=q_{1}q_{2}q_{3}\dots q_{t}-p_{1}q_{2}q_{3}\dots q_{t}=m-p_{1}q_{2}q_{3}\dots q_{t}<m\;$.
Dimostriamo ora che $n$ ammette almeno due fattorizzazioni distinte.
Iniziamo considerando il primo fattore di $n$, $q_{1}-p_{1}$. Esso può essere primo o meno; nel caso non lo fosse lo fattorizzeremo e la nuova fattorizzazione di $n$ così ottenuta non ammetterebbe $p_{1}$ tra i suoi fattori. Infatti, per la prima parte della dimostrazione sappiamo che $p_{1}$ è diverso da $q_{2},q_{3},\dots q_{t}$ e non può comparire nella eventuale fattorizzazione di $q_{1}-p_{1}$, poiché se ciò accadesse significherebbe che
    $q_{1}-p_{1}=p_{1}\cdot b\Rightarrow q_{1}=p_{1}(1+b)$
e quindi $q_{1}$ sarebbe divisibile per $p_{1}$, il che non è possibile in quanto $q_{1}$ è un numero primo.
Prendendo ora l'ultima uguaglianza della $\left[4\right]$ e sostituendo $m$ con la $\left[1\right]$ otteniamo
    $\left[5\right]\quad n=p_{1}p_{2}p_{3}\dots p_{s}-p_{1}q_{2}q_{3}\dots q_{t}\Rightarrow n=p_{1}(p_{2}p_{3}\dots p_{s}-q_{2}q_{3}\dots q_{t})$
In qualunque modo sia fattorizzabile il secondo fattore nella $\left[5\right]$, avremo ottenuto una fattorizzazione di $n$ che contiene $p_{1}$ e che pertanto è diversa da quella nella $\left[3\right]$, contrariamente all'ipotesi che $m$ sia il numero più piccolo che ammette più di una fattorizzazione.
L'unicità è pertanto dimostrata.