Introduzione ai Numeri Primi

I Numeri Primi sono un importante classe di numeri naturali che hanno un ruolo fondamentale in matematica e in informatica.

Le loro proprietà hanno affascinato e ispirato matematici e scienziati sin dall'antichità.

In questa lezione introduttiva daremo la definizione di numero primo e vedremo che i numeri primi sono infiniti.

I numeri primi

I numeri primi sono numeri naturali maggiori di 1 che hanno esattamente due divisori: 1 e se stessi. I numeri primi sono la base della Teoria dei Numeri e sono stati studiati sin dall'antichità.

Ad esempio, il numero 23 è un numero primo in quanto è divisibile esclusivamente per 1 e per se stesso.

Viceversa, se prendiamo il numero 33, possiamo notare che è divisibile per 1, 3, 11 e 33. Quindi il numero 33 non è un numero primo.

Definizione

Numero Primo

Un Numero Primo è un numero naturale maggiore divisibile solo per 1 e per se stesso.

Formalmente:

n \in \mathbb{N} \quad \text{è primo} \iff \nexists\, a, b \in \mathbb{N} \quad \text{tali che} \quad n = a \cdot b \quad \text{con} \quad 1 < a, b < n è

I numeri primi minori di 100 sono riportati di seguito:

\begin{array}{ccccccccc} 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 \\ 29 & 31 & 37 & 41 & 43 & 47 & 53 & 59 & 61 \\ 67 & 71 & 73 & 79 & 83 & 89 & 97 \end{array}

Un numero non primo prende il nome di numero composto.

Definizione

Numeri Composti

Un Numero Composto è un numero naturale maggiore di 1 che ha più di due divisori, ossia è divisibile per almeno un numero diverso da 1 e da se stesso.

Data la definizione di numero primo, possiamo suddividere l'insieme dei numeri naturali \mathbb{N} in tre sotto-insiemi disgiunti, come mostra la figura che segue:

Suddivisione dell'insieme dei numeri naturali
Figura 1: Suddivisione dell'insieme dei numeri naturali

I sotto-insiemi sono:

  • L'insieme costituito da tutti i numeri primi;
  • l'insieme costituito da tutti i numeri composti;
  • l'insieme composto dai soli numeri 0 e 1.

Bisogna notare l'ultimo insieme, costituito dai soli numeri 0 e 1. Questi due numeri non sono né primi né composti.

Il numero 0 non è composizione di nessun numero naturale, mentre il numero 1 è divisibile solo per se stesso.

Definizione

Numeri 0 e 1

I due numeri 0 e 1 non sono né primi né composti.

I numeri primi sono infiniti

Proviamo a scorrere la lista dei numeri primi minori di 300:

\begin{array}{ccccccccc} 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 \\ 29 & 31 & 37 & 41 & 43 & 47 & 53 & 59 & 61 \\ 67 & 71 & 73 & 79 & 83 & 89 & 97 & 101 & 103 \\ 107 & 109 & 113 & 127 & 131 & 137 & 139 & 149 & 151 \\ 157 & 163 & 167 & 173 & 179 & 181 & 191 & 193 & 197 \\ 199 & 211 & 223 & 227 & 229 & 233 & 239 & 241 & 251 \\ 257 & 263 & 269 & 271 & 277 & 281 & 283 & 293 \end{array}

La prima cosa che si nota è che i numeri primi non sono distribuiti in modo regolare. Ad esempio, tra il numero 2 e il numero 3 non ci sono altri numeri primi, tra il numero 41 e 43 ce n'è uno solo, mentre tra il numero 199 e il numero 211 ce ne sono ben 11.

Allo stato attuale delle nostre conoscenze, non esiste una formula che permetta di calcolare i numeri primi. E tanto meno non esiste un modo che ne descriva la distribuzione. Per quanto ne sappiamo, i numeri primi sono distribuiti in modo casuale.

Questo è uno dei motivi per cui i numeri primi sono così affascinanti e hanno attirato l'attenzione di matematici e scienziati per secoli.

Un'altra cosa che si nota mano a mano che si scorre la lista dei numeri primi è che i numeri primi diventano sempre più rari. Sembra quasi come se essi diminuiscano e sia più difficile trovarli.

Ad esempio, se prendiamo intervalli di 100 numeri, possiamo notare che il numero di numeri primi diminuisce:

  • I numeri primi compresi tra 1 e 100 sono 25;
  • I numeri primi compresi tra 101 e 200 sono 21;
  • I numeri primi compresi tra 201 e 300 sono 16.

Se andiamo più in la notiamo che essi diventano sempre più rari:

  • I numeri primi compresi tra 2001 e 2100 sono 14;
  • I numeri primi compresi tra 2101 e 2200 sono 10;
  • I numeri primi compresi tra 1000001 e 1000100 sono solo 6.

Questa stranezza ha portato i matematici, sin dall'antichità, a chiedersi se, prima o poi, i numeri primi si esauriscano. In altre parole, i numeri primi sono infiniti oppure esiste un numero primo che sia il più grande di tutti gli altri? La risposta a questa domanda è stata data solo nel 300 a.C. da Euclide.

Egli infatti scrisse negli Elementi, Libro IX, Proposizione 20:

Esistono sempre numeri primi in numero maggiore di quanti numeri primi si vogliano proporre.

Definizione

I numeri primi sono infiniti

Sebbene non sia nota una formula che permetta di calcolare i numeri primi o di prevedere la loro distribuzione, è possibile dimostrare che i numeri primi sono infiniti.

L'osservazione di Euclide

Il primo a dimostrare che i numeri primi sono infiniti fu Euclide nel 300 a.C.

La sua dimostrazione è un classico esempio di dimostrazione per assurdo e si basa su un'osservazione molto semplice.

Proviamo a prendere i primi due numeri primi, 2 e 3, li moltiplichiamo tra di loro e aggiungiamo 1:

n = 2 \cdot 3 + 1 = 7

Abbiamo trovato un numero primo, 7, che non è né 2 né 3. Anzi, 7 è maggiore di entrambi.

Ripetiamo il procedimento con i primi tre numeri primi, 2, 3 e 5:

n = 2 \cdot 3 \cdot 5 + 1 = 31

Anche in questo caso abbiamo trovato un numero primo, 31, maggiore di quelli considerati.

Proviamo a proseguire con i primi quattro numeri primi, 2, 3, 5 e 7:

n = 2 \cdot 3 \cdot 5 \cdot 7 + 1 = 211

Di nuovo abbiamo trovato un numero primo, 211, maggiore di quelli usati.

Riproviamo con i primi cinque numeri primi, 2, 3, 5, 7 e 11:

n = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 + 1 = 2311

Anche 2311 è un numero primo ed è maggiore di tutti i numeri primi considerati.

A questo punto potremmo essere portati a pensare che basta moltiplicare una sequenza di numeri primi e aggiungere 1 per ottenerne un altro. Ma questo non è vero.

Infatti, se proviamo a ripetere il procedimento con i primi sei numeri primi, 2, 3, 5, 7, 11 e 13, otteniamo:

n = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031

Il numero 30031 non è primo. Infatti, esso è divisibile per 59 e 509.

Tuttavia, se osserviamo bene, i numeri 59 e 509 sono primi e sono maggiori di quelli considerati.

Questo ci suggerisce che, se prendiamo un numero primo p e moltiplichiamo tutti i numeri primi minori di p e aggiungiamo 1, si possono verificare due casi:

  1. Il numero ottenuto è primo e maggiore di p;
  2. Il numero ottenuto è composto e ha almeno un divisore primo maggiore di p.

In entrambi i casi, esiste un numero primo maggiore di p.

Questo ragionamento può essere ripetuto all'infinito dimostrando che i numeri primi sono infiniti.

Dimostrazione di Euclide

Adesso vediamo la dimostrazione di Euclide in modo più formale.

Dimostrazione

Dimostrazione dell'infinità dei numeri primi

Vogliamo dimostrare che l'insieme dei numeri primi, che indichiamo con P, sia infinito.

Procedendo per assurdo, supponiamo che esista un numero primo p che sia maggiore di tutti gli altri numeri primi.

Formalmente, supponiamo che:

\exists\, p \in P \quad \text{tale che} \quad p > q \quad \forall q \in P \quad \text{con} \quad q \neq p

Adesso, consideriamo il numero naturale n così costruito:

n = \left( p_1 \cdot p_2 \cdot p_3 \cdot \ldots \cdot p \right) + 1

In altre parole, n è il prodotto di tutti i numeri primi minori o uguali di p più 1.

Possiamo riscrivere n come:

n = \left( 2 \cdot 3 \cdot 5 \cdot 7 \cdot \ldots \cdot p \right) + 1

Dal momento che, per costruzione, n è un numero maggiore di 1, esso deve essere divisibile per almeno un numero primo (incluso se stesso). In altre parole o n è un numero primo oppure n è un numero composto.

Andiamo, quindi, per ordine:

  • Il numero n non è divisibile per 2 in quanto il resto della divisione di n per 2 è 1;
  • Analogamente, il numero n non è divisibile per 3 in quanto il resto della divisione di n per 3 è 1;
  • E così via per tutti i numeri primi minori o uguali a p.

Infatti, il resto della divisione di n per uno qualsiasi dei numeri primi minori o uguali a p è sempre 1.

Ne consegue che nessuno dei numeri primi minori o uguali a p divide n, incluso lo stesso p.

Allora possono verificarsi due casi:

  1. Il numero n è primo;
  2. Il numero n è composto ma ha almeno un divisore q primo maggiore di p.

In entrambe i casi, abbiamo trovato un numero primo maggiore di p.

Ciò contraddice l'ipotesi iniziale che p fosse il più grande numero primo.

E poiché a partire da un numero primo p ne possiamo sempre trovare uno maggiore in questo modo, possiamo concludere che l'insieme dei numeri primi è infinito.

In Sintesi

In questa lezione abbiamo introdotto i Numeri Primi.

Abbiamo visto che:

  • Un numero primo è un numero naturale maggiore di 1 che ha esattamente due divisori: 1 e se stesso;
  • Un numero composto è un numero naturale maggiore di 1 che ha più di due divisori;
  • I numeri primi sono infiniti.

Nella prossima lezione vedremo un procedimento per enumerare, ossia elencare, tutti i numeri primi minori di un dato numero. Questo procedimento è noto come Crivello di Eratostene.

Indice del capitolo Lezione Successiva