[next] [prev] [prev-tail] [tail] [up]

Capitolo 11
Numeri primi e fattorizzazione

WEB (Materiali vari)

“

Studia questo capitolo con l’AI: quiz, esercizi e altro

Ripassa con le flashcard

Esercizi auto-generati

Sorgente di questo capitolo

Schede, test e video di matematika.it

I numeri primi crescono come la gramigna tra i numeri naturali, soggetti soltanto al caso, eppure obbediscono a leggi sorprendentemente esatte.”

— Don Zagier, The First 50 Million Prime Numbers (1975)

____________________________________________________________________________________

11.1 Introduzione motivazionale

quiz e materiali con l’AI

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.

11.2 Definizione di numero primo

quiz e materiali con l’AI

flashcard del paragrafo

Definizione 11.1 — Numero primo

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.

11.3 Crivello di Eratostene

quiz e materiali con l’AI

flashcard del paragrafo

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.

[Picture]

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.

11.4 Teorema fondamentale dell’aritmetica

quiz e materiali con l’AI

flashcard del paragrafo

Teorema 11.3 — Teorema fondamentale dell’aritmetica

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

Esempio 11.2 — Fattorizzazioni notevoli

11.5 Scomposizione in fattori primi

quiz e materiali con l’AI

flashcard del paragrafo

Procedura  — Scomporre un numero in fattori primi

1.
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}\).)

Esempio 11.3 — Scomposizione di \(360\)

Determinare la scomposizione di \(360\).

Soluzione.

\[ \begin {array}{r|l} 360 & 2 \\ 180 & 2 \\ 90 & 2 \\ 45 & 3 \\ 15 & 3 \\ 5 & 5 \\ 1 & \\ \end {array} \]

Allora \(360 = 2^3\cdot 3^2\cdot 5\).

[Picture]

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\).

11.6 MCD e mcm con fattorizzazione

quiz e materiali con l’AI

flashcard del paragrafo

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:

\[ \operatorname{MCD} (a,b) = \prod _{i=1}^k p_i^{\min (\alpha _i,\beta _i)}, \qquad \operatorname{mcm} (a,b) = \prod _{i=1}^k p_i^{\max (\alpha _i,\beta _i)}. \]

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.

Esempio 11.4

\(a=60=2^2\cdot 3\cdot 5\), \(b=84=2^2\cdot 3\cdot 7\).

\begin{align*} \operatorname{MCD} (60,84) &= 2^2\cdot 3 = 12, \\ \operatorname{mcm} (60,84) &= 2^2\cdot 3\cdot 5\cdot 7 = 420. \end{align*}

Verifica: \(\operatorname{MCD} \cdot \operatorname{mcm} = 12\cdot 420 = 5\,040 = 60\cdot 84\). \(\checkmark\)

Nota  — Coprimi e fattorizzazioni disgiunte

\(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\).

11.7 Esempi svolti

quiz e materiali con l’AI

Esempio 11.5 — Test di primalità

Stabilire se \(251\) è primo.

Soluzione. \(\sqrt {251}\approx 15{,}8\), quindi basta provare a dividere \(251\) per i primi \(\le 15\): \(2, 3, 5, 7, 11, 13\).

Nessuno divide \(251\), dunque \(251\) è primo.

Esempio 11.6 — Scomposizione di un numero grande

Scomporre in fattori primi \(2310\).

Soluzione.

\[ 2310 = 2\cdot 1\,155 = 2\cdot 3\cdot 385 = 2\cdot 3\cdot 5\cdot 77 = 2\cdot 3\cdot 5\cdot 7\cdot 11. \]

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:

\[ 1,2,3,4,5,6,8,9,10,12,15,18,20,24,30,36,40,45,60,72,90,120,180,360. \]

Esempio 11.8 — Calcolo combinato di MCD e mcm

Calcolare \(\operatorname{MCD} (168, 180, 210)\) e \(\operatorname{mcm} (168, 180, 210)\).

Soluzione. Scomponiamo:

\[ 168 = 2^3\cdot 3\cdot 7,\quad 180 = 2^2\cdot 3^2\cdot 5,\quad 210 = 2\cdot 3\cdot 5\cdot 7. \]

Fattori comuni a tutti e tre: \(2\) e \(3\). Esponenti minimi: \(2^1\) e \(3^1\).

\[ \operatorname{MCD} (168,180,210) = 2\cdot 3 = 6. \]

Tutti i fattori presenti: \(2,3,5,7\). Esponenti massimi: \(2^3, 3^2, 5, 7\).

\[ \operatorname{mcm} (168,180,210) = 2^3\cdot 3^2\cdot 5\cdot 7 = 2\,520. \]

Esempio 11.9 — Distribuzione irregolare dei primi

Quanti primi ci sono tra \(1\) e \(100\)? E tra \(101\) e \(200\)?

Soluzione. Con il crivello (o consultando una tabella):

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}\).

11.8 Esercizi proposti

quiz e materiali con l’AI

Esercizio 11.1

1.
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\).
2.
Scomponi in fattori primi: (a) \(126\); (b) \(300\); (c) \(504\); (d) \(2024\); (e) \(4900\); (f) \(30030\).
3.
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\).

11.9 Riepilogo del capitolo

quiz e materiali con l’AI

[next] [prev] [prev-tail] [front] [up]