Gioca con la matematica: i numeri primi - Matematica NON Antipatica

Ti piacciono i numeri primi?

Non dirmi che non sai cosa sono i numeri primi!

I numeri primi sono quei numeri che hanno come divisori soltanto 1 e se stessi. Tutti i numeri che non sono primi, vengono definiti composti.

Sono dunque primi i numeri

$2, 3, 5, 7, 11, 13, 17,\ldots$

mentre sono composti i numeri

$4, 6, 8, 9, 10, 12, 14, \ldots$

Quanti sono i numeri primi? Infiniti, come dimostrò Euclide nel 300 A.C.! Vediamo la dimostrazione:

supponiamo che i numeri primi non siano infiniti ma solo $n$ . Consideriamo l’insieme ordinato di tali numeri:

$p_1,p_2,p_3,\ldots ,p_n$

$p_n$ è il numero primo più grande di tutti.

Consideriamo ora il numero

$p=p_1 \cdot p_2 \cdot p_3 \ldots\cdot p_n$

Il numero $p$ è sicuramente maggiore di ciascuno dei numeri, e quindi anche di $p_n$ :

$p>p_n$

A maggior ragione aggiungendo 1:

$p+1>p_n$

Il teorema fondamentale dell’aritmetica ci dice che un numero o è primo o è ottenuto dal prodotto di numeri primi.

Allora le possibilità sono due:

$p+1$ è un numero primo. Ne consegue allora che $p_n$ non è il maggiore dei numeri primi

$p+1$ è un numero composto. Ma allora deve essere necessariamente divisibile per un divisore. Ma non può essere diviso per nessuno dell’insieme $p_1, p_2,\ldots,p_n$ in quanto la divisione da sempre resto 1. Immaginiamo ad esempio di considerare l’insieme $2,3,5,7$ :

$p=2 \cdot 3 \cdot5 \cdot 7=210$

$p+1=211$ .

Il resto della divisione tra 211 e uno dei fattori di $p$ è pari ad uno:

$211:2=105$ con resto 1

$211:3=70$ con resto 1

$211:5=42$ con resto 1

$211:7=30$ con resto 1

Visto che $p_n$ è composto, deve allora necessariamente esistere un numero primo più grande di $p_n$ , perchè diverso da tutti quelli considerati.

I numeri primi affascinano sin dall’antichità, e non solo Euclide. Uno tra i più rinomati ed antichi algoritmi per individuare i numeri primi è il crivello di Eratostene. Esso consente di trovare tutti i numeri primi minori o uguali ad un prefissato numero. Come funziona?

Possiamo pensarlo come un setaccio, che una volta riempito di numeri, lascia cadere solo i numeri composti.

Considerata una lista ove ricercare i numeri primi, si cancellano (si setacciano) dapprima i numeri multipli di 2. Poi si considera il primo numero non cancellato maggiore di 2 e si ripete l’operazione, setacciando i suoi multipli. Si prosegue sino all’ultimo numero non cancellato: i numeri restanti sono i numeri primi cercati.

Facciamo un esempio, andando a scoprire i numeri primi minori di 26. Come primo passo, scriviamo tutti i numeri interi da 2 a 25:

Poi, cancelliamo dalla lista i multipli di 2 (i numeri setacciati sono: 4,6,8,10,12,14,16,18,20,22,24). Otteniamo quindi:

Il numero successivo al 2 è il 3: cancelliamo dalla lista tutti i multipli di 3 (i numeri setacciati sono 9, 15,21). Otteniamo il seguente elenco:

Dopo il 3 è la volta dei multipli del 5. Escludendo il numero 25 (l’unico setacciato), abbiamo:

Non essendoci più multipli dopo il 5, i numeri ottenuti sono i numeri primi cercati.

Eulero, invece, trovò una formula per i numeri primi. Formula in grado di determinarne un numero rilevante (ma non ricavarli tutti!):

$a^2+a+41, a \in \mathbb{N}$

A Eulero va anche il merito di aver dimostrato un importante teorema sui numeri primi, enunciato da Fermat. I numeri primi, possono essere di due tipologie:

primo tipo: $4n+1$

secondo tipo: $4n-1$

Ove $n \in \mathbb{Z}$

Fermat affermava che quelli del primo tipo sono la somma di due quadrati mentre quelli del secondo non sono esprimibili in tal modo.

Per il primo tipo, se ad esempio $n=3$ :

$4 \cdot 3 + 1=13$

$13=2^2+3^2$

Eulero, dopo anni di lavoro, dimostro il teorema.

Insomma, i numeri primi attiravano e continuano ad attirare l’attenzione di molti matematici. Il numero primo più grande, ad oggi scoperto è:

$2^{77.232.917}-1$

Un numero di oltre 23 milioni di cifre!

L’Electronic Frontier Foundation ha addirittura messo in palio 150 mila dollari per chi troverà un numero primo da cento milioni di cifre e 250 mila dollari a chi riuscirà a trovare un numero primo di un miliardo di cifre!

Valutare se un numero molto grande è primo oppure no, non è per niente semplice. Però possono esserci di aiuto i criteri di divisibilità!

Ad esempio, tutti i numeri pari (ad eccezione del 2) non sono numeri primi visto che hanno come divisore il 2.

Ricordiamo i criteri di divisibilità? Vediamone alcuni:

Numeri divisibili per 2: un numero è divisibile per 2 se è pari, oppure, in maniera equivalente, se la sua ultima cifra è pari (0, 2, 4, 6, 8).

Numeri divisibili per 3: un numero è divisibile per 3 quando la somma delle sue cifre è divisibile per 3, ovvero se la somma delle sue cifre è multiplo di 3:

1437 è divisibile per 3 in quanto

$1+4+3+7=15$

e 15 è multiplo di 3.

Numeri divisibili per 4: un numero è divisibile per 4 se le ultime due cifre sono 00 oppure formano un numero multiplo di 4. Esempio:

412 è divisibile per 4 dato che le sue ultime due cifre costituiscono il numero 12 che è multiplo di 4.

Numeri divisibili per 5: un numero è divisibile per 5, se la sua ultima cifra è 0 o 5. Esempio:

6820 ha come ultima cifra lo zero, quindi è divisibile per 5.

Numeri divisibili per 6: un numero è divisibile per 6 se è contemporaneamente divisibile per 2 e per 3. Esempio:

738 è divisibile per 2, essendo la sua ultima cifra pari. E’ divisibile anche per 3, visto che la somma delle sue cifre è multiplo di 3. Quindi è divisibile per 6.

Numeri divisibili per 7: un numero è divisibile per 7 se la differenza tra il numero senza la cifra delle unità e il doppio di quest’ultima è 0, 7 oppure un multiplo di 7. Esempio:

763 è divisibile per 7 visto che

$76-2\cdot3=70$

Numeri divisibili per 8: un numero è divisibile per 8 se le sue ultime tre cifre costituiscono un numero divisibile per 8 oppure sono tre zeri. Esempio:

$1256$

Il numero ottenuto isolando le ultime tre cifre è divisibile per 8:

$256=32 \cdot 8$

Numeri divisibili per 9: un numero è divisibile per 9 se la somma delle sue cifre è 9 o un multiplo di 9. Esempio:

$1395$

$1+3+9+5=18$

18 multiplo di 9.

Numeri divisibili per 10: un numero è divisibile per 10 se la sua ultima cifra è 0. Esempio:

$8950$

Numeri divisibili per 11: un numero è divisibile per 11 se la differenza tra la somma delle cifre di posto pari e la somma delle cifre di posto dispari è in valore assoluto 11, un muliplo di 11 oppure è zero. Esempio:

$6534$

Somma delle cifre di posto pari:

$5+4=9$

Somma delle cifre di posto dispari:

$6+3=9$

Sottraendo il risultato:

$9-9=0$

Abbiamo quindi uno strumento per capire se un numero è primo oppure no. Ad esempio, 9813 è un numero primo? Certo che no, visto che è divisibile per 3:

$9+8+1+3=21$

21 multiplo di 3.

Vuoi conoscere tutti i numeri primi minori di 10000? Scaricali in Excel!

Scarica i numeri primi

Impara e divertiti scoprendo aneddoti, curiosità sulla matematica e confrontandoti con giochi e problemi!

Non un semplice play, ma PintaPlay!

Commenta questo post

Il fascino dei numeri primi

Post correlati: