Vai al contenuto
Topos Uranos
Italiano

Numeri primi e teorema fondamentale dell’aritmetica

Riepilogo

Questa lezione studia i numeri primi, gli atomi della moltiplicazione dei naturali. Dimostra che ogni naturale maggiore di 11 ha un divisore primo, presenta il crivello di Eratostene e la ragione per cui basta setacciare fino alla radice quadrata, e prova con Euclide che i primi sono infiniti. Dimostra poi il lemma di Euclide, secondo il quale un primo che divide un prodotto divide uno dei suoi fattori, e con esso il teorema fondamentale dell’aritmetica: ogni naturale maggiore di 11 si scrive come prodotto di primi in un unico modo. Dalla fattorizzazione si deducono il numero dei divisori di un naturale, la caratterizzazione dei quadrati perfetti e l’irrazionalità della radice quadrata di ogni naturale che non sia un quadrato perfetto.

Obiettivi di apprendimento

  1. Distinguere i numeri primi dai composti e dimostrare che ogni naturale maggiore di 11 ha un divisore primo.
  2. Applicare il crivello di Eratostene e giustificare perché basta cancellare i multipli dei primi non maggiori della radice quadrata del limite.
  3. Dimostrare l’infinità dei primi, il lemma di Euclide e l’esistenza e l’unicità della fattorizzazione in primi.
  4. Usare la fattorizzazione per contare ed elencare divisori, riconoscere quadrati perfetti e dimostrare l’irrazionalità di radici quadrate.

Numeri primi e numeri composti

Nella lezione sulla divisibilità e la divisione con resto si è visto che ogni naturale nn è divisibile per 11 e per sé stesso. Alcuni naturali non ammettono altri divisori oltre a questi due; sono i pezzi con cui, per moltiplicazione, si compongono tutti gli altri.

Definizione (numero primo). Un naturale pp è primo se p>1p > 1 e i suoi unici divisori sono 11 e pp. Un naturale n>1n > 1 che non è primo si dice composto: si scrive come n=abn = ab, con 1<a<n1 < a < n e 1<b<n1 < b < n. Il numero 11 non è né primo né composto.

I primi minori di 5050 sono i quindici seguenti:

2,3,5,7,11,13,17,19,23,29,31,37,41,43,472, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Il 22 è l’unico primo pari, perché ogni altro numero pari ha il divisore 22, distinto da 11 e da sé stesso. L’esclusione dell’11 non è un capriccio della definizione: se 11 fosse primo, la fattorizzazione in primi cesserebbe di essere unica, perché 6=2⋅3=1⋅2⋅36 = 2 \cdot 3 = 1 \cdot 2 \cdot 3, e il teorema centrale di questa lezione dovrebbe essere enunciato con un’eccezione.

Il principio del buon ordinamento

Le dimostrazioni di questa lezione si appoggiano a una forma del principio di induzione particolarmente comoda per ragionare sui divisori: il principio del buon ordinamento, secondo il quale ogni insieme non vuoto di numeri naturali ha un elemento minimo. È stato dedotto dall’induzione forte nella lezione su sommatorie, progressioni e induzione, e qui si usa senza ripeterne la dimostrazione.

Ogni naturale maggiore di 1 ha un divisore primo

Il primo risultato della lezione assicura che nessun naturale maggiore di 11 sfugge ai primi: ce n’è sempre uno che lo divide, e lo si trova tra i divisori più piccoli.

ProposizioneIl minimo divisore maggiore di 1 è primo

Ogni naturale n>1n > 1 ha un divisore primo: il minimo divisore di nn maggiore di 11 è primo. Se inoltre nn è composto, il suo minimo divisore primo pp soddisfa p2≤np^2 \leq n. La figura segna sulla retta i divisori di n=91=7⋅13n = 91 = 7 \cdot 13.

Dimostrazione

  1. D={d∈N:d∣n∧d>1},n∈D,m=min⁡D\dato{D}{D = \{ d \in \mathbb{N} : d \mid n \wedge d > 1 \}}, \quad n \in D, \quad m = \min D

    L’insieme dei divisori di nn maggiori di 11 non è vuoto, perché contiene nn stesso; per il principio del buon ordinamento, ha un elemento minimo mm.

  2. a∣m∧m∣n→a∈D,a<ma \mid m \wedge m \mid n \rightarrow \resaltar{a \in D}, \quad \resaltar{a < m}

    Se mm fosse composto, m=abm = ab con 1<a<m1 < a < m, il fattore aa dividerebbe mm e, per la transitività della divisibilità, nn: sarebbe un elemento di DD minore di mm, contro la scelta di mm. Pertanto, mm è primo.

  3. n=pk,k∈D\dato{k}{n = pk, \quad k \in D}

    Sia ora nn composto, e sia pp il suo minimo divisore primo, che è l’elemento minimo di DD. Scriviamo n=pkn = pk; poiché nn non è primo, k≠1k \neq 1, e anche kk divide nn.

  4. p2=p⋅p≤p⋅k=np^2 = p \cdot p \leq \resaltar{p \cdot k} = n

    Per la minimalità di pp, si ha k≥pk \geq p, e la monotonia della moltiplicazione dà la stima.

Pertanto, per decidere se un naturale nn è primo basta provare i primi pp con p2≤np^2 \leq n: se nessuno lo divide, nn è primo. Per esempio, per 221221 basta provare i primi fino a 1313, perché 172=289>22117^2 = 289 > 221: non è divisibile per 22, 33, 55, 77 né 1111, ma lo è per 1313, e 221=13⋅17221 = 13 \cdot 17. Invece 211211 non è divisibile per nessuno dei primi 22, 33, 55, 77, 1111 e 1313, e poiché 172=289>21117^2 = 289 > 211, il numero 211211 è primo.