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
mentre sono composti i numeri
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 . Consideriamo l’insieme ordinato di tali numeri:
è il numero primo più grande di tutti.
Consideriamo ora il numero
Il numero è sicuramente maggiore di ciascuno dei numeri, e quindi anche di
:
A maggior ragione aggiungendo 1:
Il teorema fondamentale dell’aritmetica ci dice che un numero o è primo o è ottenuto dal prodotto di numeri primi.
Allora le possibilità sono due:
è un numero primo. Ne consegue allora che
non è il maggiore dei numeri primi
è un numero composto. Ma allora deve essere necessariamente divisibile per un divisore. Ma non può essere diviso per nessuno dell’insieme
in quanto la divisione da sempre resto 1. Immaginiamo ad esempio di considerare l’insieme
:
.
Il resto della divisione tra 211 e uno dei fattori di è pari ad uno:
con resto 1
con resto 1
con resto 1
con resto 1
Visto che è composto, deve allora necessariamente esistere un numero primo più grande di
, 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 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:
secondo tipo:
Ove
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 :
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 è:
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
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
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:
Il numero ottenuto isolando le ultime tre cifre è divisibile per 8:
Numeri divisibili per 9: un numero è divisibile per 9 se la somma delle sue cifre è 9 o un multiplo di 9. Esempio:
18 multiplo di 9.
Numeri divisibili per 10: un numero è divisibile per 10 se la sua ultima cifra è 0. Esempio:
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:
Somma delle cifre di posto pari:
Somma delle cifre di posto dispari:
Sottraendo il risultato:
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:
21 multiplo di 3.
Vuoi conoscere tutti i numeri primi minori di 10000? Scaricali in Excel!
Impara e divertiti scoprendo aneddoti, curiosità sulla matematica e confrontandoti con giochi e problemi!
Non un semplice play, ma PintaPlay!