Il fascino dei numeri primi

    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