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!

 

  • Matematica NON Antipatica

    Matematica NON Antipatica vuole guidare gli studenti alla scoperta di una matematica applicata, affinchè comprendano appieno il senso del processo formativo scolastico e sviluppino una maggiore propensione all'apprendimento. High School, High Future.

 

Commenta questo post