I numeri primi sono i mattoni della matematica: ogni intero più grande di \(1\) si può costruire
moltiplicando un certo numero di primi, in un solo modo possibile. È un’affermazione di
una semplicità sorprendente, eppure è la base di un’intera disciplina — la teoria dei
numeri — e di applicazioni quotidiane come la crittografia che protegge i conti correnti
online.
Eppure i primi sono distribuiti in modo apparentemente caotico: dopo \(2, 3, 5, 7, 11\) si trovano i due
“gemelli” \(11\) e \(13\), poi \(17, 19, 23, 29\)…Si dirada il loro ritmo, ma non si esauriscono mai: già Euclide dimostrò, nel iii
sec. a.C., che i primi sono infiniti.
In questo capitolo riprendiamo la definizione di primo, presentiamo il crivello di Eratostene
(l’algoritmo più antico per trovarli), enunciamo il teorema fondamentale dell’aritmetica (l’esistenza
e unicità della fattorizzazione), e impariamo a usare la scomposizione in primi per calcolare MCD e
mcm in modo sistematico.
Un numero naturale \(p\ge 2\) si dice primo se ha esattamente due divisori positivi: \(1\) e \(p\) stesso.
Definizione 11.2 — Numero composto
Un numero naturale \(n\ge 2\) si dice composto se non è primo: ammette almeno un divisore
positivo \(d\) con \(1<d<n\).
Attenzione! — Il caso \(1\)
Il numero \(1\) non è primo né composto: ha un solo divisore positivo (sé stesso). Escluderlo
dai primi è una scelta motivata: serve a garantire l’unicità della fattorizzazione (vedi più
avanti). Se \(1\) fosse primo, \(6=2\cdot 3\) ma anche \(6=1\cdot 2\cdot 3 = 1\cdot 1\cdot 2\cdot 3\), con infinite varianti.
Esempio 11.1
I primi numeri primi sono \(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, \ldots \) \(2\) è l’unico primo pari: ogni altro pari è divisibile per \(2\) e dunque ammette almeno il divisore
\(2\), oltre a \(1\) e a sé stesso. I primi numeri composti sono \(4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, \ldots \)
Teorema 11.1 — Infinità dei numeri primi
L’insieme dei numeri primi è infinito.
La dimostrazione, già vista nel capitolo 6, è di Euclide: si suppone per assurdo che i primi siano \(p_1,\ldots ,p_n\)
e si considera \(N=p_1\cdots p_n+1\), che porta a una contraddizione.
Teorema 11.2 — Lemma di Euclide
Sia \(p\) un numero primo e \(a,b\in \mathbb{Z} \). Se \(p\mid a\cdot b\), allora \(p\mid a\) oppure \(p\mid b\).
Dimostrazione (idea). Se \(p\nmid a\), allora \(\operatorname{MCD} (p,a)=1\) (perché i soli divisori di \(p\) sono \(1\) e \(p\) stesso). Esistono dunque \(x,y\in \mathbb{Z} \)
con \(px+ay=1\) (identità di Bézout, che riprenderemo in \(\mathbb{R} \) nel capitolo 131). Moltiplicando per \(b\): \(pxb+aby=b\). Poiché \(p\mid pxb\) e \(p\mid aby\)
(per ipotesi), \(p\mid b\).
Nota
Il lemma di Euclide è cruciale: è esattamente la proprietà che distingue i primi dai
composti. Se \(n=6\) non è primo, può succedere che \(6\mid 4\cdot 9=36\) ma \(6\nmid 4\) e \(6\nmid 9\). La proprietà \(p\mid ab\Rightarrow p\mid a\lor p\mid b\) è specifica dei primi.
Esiste un metodo molto antico, attribuito a Eratostene (iii sec. a.C.), per trovare tutti i primi
minori di un dato numero \(N\). L’idea è “setacciare” i composti, cancellandoli sistematicamente dalla
lista dei naturali \(2, 3, \ldots , N\).
Procedura — Crivello di Eratostene
Per trovare tutti i primi \(\le N\):
1.
Si scrivono i numeri da \(2\) a \(N\).
2.
Il primo numero non cancellato è \(2\): lo si marca come primo e si cancellano tutti i suoi
multipli (\(4, 6, 8, \ldots \)).
3.
Il successivo non cancellato è \(3\): lo si marca come primo e si cancellano i suoi multipli
(\(6, 9, 12, \ldots \), se non già cancellati).
4.
Si prosegue con il successivo non cancellato (\(5\), poi \(7\), poi \(11\), …), marcandolo come primo
e cancellandone i multipli.
5.
Ci si può fermare quando il primo da marcare è \(>\sqrt {N}\): tutti i non cancellati rimasti sono
primi.
Nota — Perché basta arrivare a \(\sqrt {N}\)
Se \(n\le N\) è composto, \(n=a\cdot b\) con \(1<a\le b<n\). Allora \(a^2\le ab = n\le N\), dunque \(a\le \sqrt {N}\). Quindi il più piccolo divisore non banale di \(n\) è \(\le \sqrt {N}\),
ed è già stato controllato.
Figura 11.1: Crivello di Eratostene fino a \(50\). In rosso i numeri primi (\(2\), \(3\), \(5\), \(7\), \(11\), \(13\), \(17\), \(19\), \(23\), \(29\), \(31\), \(37\), \(41\), \(43\), \(47\)), in
nero i composti e l’ in rosso i primi.
Ogni numero naturale \(n\ge 2\) si può scrivere come prodotto di numeri primi. Tale scrittura è
unica, a meno dell’ordine dei fattori.
In simboli, esistono primi \(p_1<p_2<\cdots <p_k\) ed esponenti \(\alpha _1,\alpha _2,\ldots ,\alpha _k\in \mathbb{N} ^*\), univocamente determinati da \(n\), tali che
\[ n = p_1^{\alpha _1}\cdot p_2^{\alpha _2}\cdots p_k^{\alpha _k}. \]
Questa è la scomposizione in fattori primi (o fattorizzazione) di \(n\).
Nota — Cenno alla dimostrazione
Esistenza: se \(n\) è primo, \(n=n\) è la sua scomposizione. Altrimenti \(n=a\cdot b\) con \(1<a,b<n\); per induzione
(capitolo 163) entrambi si scompongono in primi, e moltiplicando le due scomposizioni
si ottiene quella di \(n\).
Unicità: se \(n=p_1\cdots p_r=q_1\cdots q_s\) sono due scomposizioni, \(p_1\mid q_1\cdots q_s\). Per il lemma di Euclide, \(p_1\) divide uno dei \(q_j\); ma
\(q_j\) è primo, dunque \(p_1=q_j\). Si semplifica e si procede per induzione. La proprietà di Euclide
è il cuore dell’unicità: senza di essa il teorema fallisce.
Si prova a dividere \(n\) per il più piccolo primo che lo divide (si parte da \(2\), poi \(3\), \(5\), \(7\), \(\ldots \) — i
primi crescenti).
2.
Si ripete sul quoziente ottenuto.
3.
Si continua finché si arriva a \(1\). I primi usati, ciascuno tante volte quanto è stato
necessario, sono i fattori primi di \(n\).
Nota — Test di primalità per tentativi
Per stabilire se un numero \(n\) è primo, basta provare a dividerlo per tutti i primi \(p\le \sqrt {n}\). Se
nessuno lo divide, \(n\) è primo. (La giustificazione è la stessa del crivello: ogni divisore non
banale di \(n\) ha un “compagno” \(\le \sqrt {n}\).)
Figura 11.2: Albero di fattorizzazione di \(60\). A ogni passo si separa un fattore primo (in rosso)
dal numero rimanente (in blu), finché si raggiungono solo primi alle foglie. Risultato: \(60 = 2\cdot 2\cdot 3\cdot 5 = 2^2\cdot 3\cdot 5\).
Riprendiamo dalla fine del capitolo 10 il metodo per calcolare MCD e mcm tramite
fattorizzazione, ora che disponiamo del teorema fondamentale.
Teorema 11.4 — MCD e mcm dalla
fattorizzazione
Siano \(a,b\in \mathbb{N} ^*\) con fattorizzazioni
\[ a = p_1^{\alpha _1}\cdot p_2^{\alpha _2}\cdots p_k^{\alpha _k},\qquad b = p_1^{\beta _1}\cdot p_2^{\beta _2}\cdots p_k^{\beta _k}, \]
dove \(p_1,\ldots ,p_k\) sono tutti i primi che compaiono in almeno uno dei due (con \(\alpha _i,\beta _i\ge 0\), e \(\alpha _i=0\) se \(p_i\) non compare
in \(a\), idem per \(b\)). Allora:
In parole: \(\operatorname{MCD} \) si ottiene prendendo solo i fattori primi comuni con esponente minimo; \(\operatorname{mcm} \) prendendo
tutti i fattori (comuni e non) con esponente massimo.
\(a\) e \(b\) sono coprimi se e solo se le loro fattorizzazioni non hanno fattori primi in comune.
In quel caso \(\operatorname{MCD} (a,b)=1\) e \(\operatorname{mcm} (a,b)=a\cdot b\).
Curiosità: \(2310=2\cdot 3\cdot 5\cdot 7\cdot 11\) è il prodotto dei primi cinque numeri primi, talvolta chiamato primoriale di
\(11\), \(11\# = 2310\).
Esempio 11.7 — Da scomposizione a divisori
Quanti divisori ha \(360\)? Elencarli tutti.
Soluzione. \(360 = 2^3\cdot 3^2\cdot 5\). Un divisore di \(360\) ha la forma \(2^a\cdot 3^b\cdot 5^c\) con \(0\le a\le 3\), \(0\le b\le 2\), \(0\le c\le 1\). Le scelte sono \(4\cdot 3\cdot 2 = 24\). Eccoli:
Primi tra \(101\) e \(200\): \(21\) numeri (\(101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199\)).
Si nota che i primi si diradano: ce ne sono via via meno in intervalli di pari lunghezza. È un
fenomeno che si quantifica con il teorema dei numeri primi (Hadamard e De La
Vallée-Poussin, 1896), molto avanzato per il liceo, che afferma: il numero di primi \(\le n\) è
asintoticamente \(\tfrac {n}{\ln n}\).
Stabilisci se sono primi o composti, motivando con un test di primalità per tentativi:
(a) \(89\); (b) \(91\); (c) \(111\); (d) \(127\); (e) \(169\); (f) \(211\).
Per ciascun numero del punto precedente, conta quanti divisori positivi ha
(suggerimento: se \(n=p_1^{\alpha _1}\cdots p_k^{\alpha _k}\), il numero di divisori è \((\alpha _1+1)\cdots (\alpha _k+1)\)).
4.
Calcola \(\operatorname{MCD} \) e \(\operatorname{mcm} \) tramite fattorizzazione: (a) \(48\) e \(80\); (b) \(90\) e \(150\); (c) \(144\), \(180\) e \(216\); (d) \(1024\) e \(2025\) (sono
coprimi?).
5.
Costruisci il crivello di Eratostene fino a \(N=60\) e indica i \(17\) primi che trovi.
6.
Trova due numeri composti consecutivi tra \(90\) e \(100\). Trova quattro numeri composti
consecutivi tra \(1\) e \(30\). (Suggerimento: ce ne sono.)
7.
Verifica che \(\operatorname{MCD} (n,n+1)=1\) per ogni \(n\in \mathbb{N} ^*\) (cioè: due naturali consecutivi sono sempre coprimi).
Suggerimento: usa l’algoritmo di Euclide.
8.
Stabilisci se le seguenti coppie sono coprime: (a) \(35\) e \(66\); (b) \(84\) e \(125\); (c) \(51\) e \(85\); (d) \(1001\) e \(1729\).
9.
(Discussione.) Un compagno afferma: “ogni primo dispari è della forma \(4k+1\) oppure \(4k+3\)”. È
vero? Trova esempi di entrambi i casi tra i primi \(\le 50\).
Un numero \(p\ge 2\) è primo se ha esattamente due divisori positivi (\(1\) e sé stesso); è composto
se ne ha più di due. \(1\) non è né primo né composto.
\(2\) è l’unico primo pari. I primi sono infiniti (Euclide, capitolo 6) e si diradano: il teorema
dei numeri primi afferma che \(\pi (n)\sim \tfrac {n}{\ln n}\) ma è ben oltre il liceo.
Lemma di Euclide: se \(p\) è primo e \(p\mid ab\), allora \(p\mid a\) o \(p\mid b\). È la proprietà che distingue i primi dai
composti.
Teorema fondamentale dell’aritmetica: ogni \(n\ge 2\) si scrive in modo unico come \(n = p_1^{\alpha _1}\cdots p_k^{\alpha _k}\) (a meno
dell’ordine dei fattori).
Crivello di Eratostene: algoritmo per trovare tutti i primi \(\le N\) cancellando
sistematicamente i multipli. È sufficiente arrivare a marcare i primi \(\le \sqrt {N}\).
Test di primalità per tentativi: per stabilire se \(n\) è primo, basta verificare che nessun
primo \(\le \sqrt {n}\) lo divida.
Da fattorizzazione a MCD/mcm: i fattori primi comuni con esponente minimo danno
\(\operatorname{MCD} \); tutti i fattori (comuni e non) con esponente massimo danno \(\operatorname{mcm} \). Conferma: \(\operatorname{MCD} \cdot \operatorname{mcm} = a\cdot b\).
Numero di divisori: se \(n=p_1^{\alpha _1}\cdots p_k^{\alpha _k}\), il numero di divisori positivi di \(n\) è \((\alpha _1+1)(\alpha _2+1)\cdots (\alpha _k+1)\).
![[Picture]](immagini_matematica/libro_matematica_a_capitoli57x.svg)
![[Picture]](immagini_matematica/libro_matematica_a_capitoli58x.svg)