Teorema fondamentale dell'aritmetica

Da Wikipedia, l'enciclopedia libera.

Il Teorema fondamentale dell'aritmetica afferma che

Ogni numero naturale diverso da 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×5×7 mentre 100 equivale a 2×2×5×5 ovvero 2²×5², ed è altrettanto facile verificare che per questi numeri non possono esistere altre scomposizioni in fattori primi.

È per unicità che il numero 1 non viene considerato primo, in quanto se lo fosse si avrebbero due o più fattorizzazioni diverse per uno stesso numero. Per esempio 10 potrebbe essere scritto come 5*2 e anche come 5*2*1 o ancora 5*2*1*1*...*1. In questo modo la proprietà di unicità non sarebbe rispettata.

Indice

1 Dimostrazione del teorema
- 1.1 Dimostrazione dell'esistenza
- 1.2 Dimostrazione dell'unicità
2 Bibliografia

[modifica] 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.

[modifica] Dimostrazione dell'esistenza

Dalla definizione di numero primo si deduce che ogni numero maggiore o uguale a 2 o è un numero primo oppure ha un divisore che è un numero primo. Questo fatto si può dimostrare per induzione:

è vero per n=2
se è vero per tutti i numeri da 2 a n allora per n+1 ci sono due possibilità: o è primo oppure è divisibile per un numero a compreso tra 2 e n, in quest'ultimo caso per l'ipotesi induttiva o a è primo o 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.

Sulla base di questo 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. Considerando n+1, abbiamo due casi:

n+1 è primo (e quindi è già fattorizzato);
n+1 è divisibile per un primo p; in questo 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=m \cdot p$ , e quindi n+1 è fattorizzabile.

Quindi, applicando il principio di induzione, l'esistenza di una fattorizzazione è vera per ogni numero naturale n.

[modifica] 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 due diverse fattorizzazioni:

$\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. (Nota: all'interno di una singola fattorizzazione ci possono essere fattori ripetuti, naturalmente: ad esempio, 100 = 2*2*5*5). Se ci fosse un fattore identico $p h = q k$ , potremmo dividere m per tale fattore e ottenere un numero $m'$ , minore di m, che avrebbe anch'esso due fattorizzazioni distinte.

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\;\!$ .

Dimostriamo ora che n ammette almeno due fattorizzazioni distinte.

Iniziamo considerando che il primo fattore di n, $q 1 - p 1$ , può o no essere primo; nel caso non lo fosse, supponiamo di fattorizzarlo. La fattorizzazione di n così ottenuta non ammette $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$ ; ma non può nemmeno comparire nella eventuale fattorizzazione di $q 1 - p 1$ . Se infatti accadesse ciò 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 per m il valore della $\left[ 1 \right]$ , otteniamo

$\left[ 5 \right] \quad n= p_1p_2p_3\dots p_s-p_1q_2q_3\dots q_t \rightarrow n = p_1(p_2p_3\dots p_s- q_2q_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 fosse il numero più piccolo che ammettesse più di una fattorizzazione.

L'unicità è pertanto dimostrata.

[modifica] Bibliografia

H. Davenport, Aritmetica superiore, Zanichelli, Bologna, 1994, ISBN 8808091546 - Capitolo I
Tom M. Apostol (1976): Introduction to Analytic Number Theory, Springer-Verlag, New York. ISBN 0-387-90163-9, (Chapter 1)