Alla ricerca dei primi
È bene precisare subito che il problema di dimostrare la primalità di un intero è cosa diversa da quella di ricercarne gli eventuali fattori. Infatti esistono dei risultati che garantiscono la primalità di un numero mediante opportune condizioni equivalenti; il fatto che tali condizioni risultino non verificate consente quindi di concludere che tale numero è composto senza doverne esibire un divisore.
Sono stati proposti diversi metodi per cercare i numeri primi. Tuttavia ognuno di questi metodi non è giunto ad una formula che consentisse di calcolare tutti i numeri primi.
Il numero primo di Fermat
Un numero primo di Fermat è un numero primo esprimibile come:
con n intero positivo. I numeri primi di Fermat prendono il nome dal matematico francese Pierre de Fermat del diciassettesimo secolo. Fermat credeva, erroneamente, che tutti i numeri della forma indicata sopra fossero numeri primi. In effetti, questo è vero per i primi cinque:
- F0 = 3
- F1 = 5
- F2 = 17
- F3 = 257
- F4 = 65.537
Eulero dimostrò che Fermat si sbagliava. Infatti il numero seguente non è primo:
F5 = 4.294.967.297 = 641 · 6.700.417
Se Fn non è un numero primo, viene detto semplicemente numero di Fermat. Attualmente, non sappiamo se ci sono altri numeri primi di Fermat per n > 10. Una curiosità: in un sistema numerico binario, tutti i primi di Fermat sono palindromi primi.
La formula di Eulero
Un’altra notevole formula che dà luogo a molti numeri primi fu scoperta da Eulero nel 1772. La formula:
x2 + x + 41
fornisce il seguente elenco di numeri primi, inserendo tutti i valori di x compresi fra 0 e 39:
41, 43, 47, 53, 61, 71, 83, 97, 113, 131, 151, 173, 197, 223, 251, 281, 313, 347,
383, 421, 461, 503, 547, 593, 641, 691, 743, 797, 853, 911, 971, 1033, 1097,
1163, 1231, 1301, 1373, 1447, 1523, 1601
Eulero comprese che il processo era destinato a interrompersi a un certo punto. Ciononostante Eulero fu molto colpito dalla capacità della sua formula di produrre tanti numeri primi, da domandarsi per quali altri numeri diversi da 41 si sarebbe potuto ottenere un risultato simile. Scoprì che si poteva scegliere anche n = 2, 3, 5, 11, 17 perché la formula x2 + x + n producesse numeri primi per ogni valore di x compreso fra 0 e n − 2.
Il numero primo di Mersenne
Un numero primo di Mersenne è un numero primo esprimibile come:
Mn = 2n - 1
con n intero positivo. I numeri primi di Mersenne prendono il nome dal matematico francese Marin Mersenne (1588-1648). Mersenne compilò una lista di numeri primi considerando tutti i valori di n, fino a n = 257. Tale lista conteneva però alcuni errori: includeva M67 e M257 (che non sono primi), mentre non comparivano M61, M89 e M107 (che sono primi). Si può sostenere che:
- Se Mn è primo, allora anche n è primo. Invece n primo non garantisce che Mn sia primo.
- Se Mn non è un numero primo, viene detto semplicemente numero di Mersenne.
La GIMPS, la Great Internet Mersenne Prime Search, è una iniziativa che sfrutta le risorse disponibili di migliaia di computer in rete per cercare i numeri primi di Mersenne. Il più grande numero primo attualmente (al 25 novembre 2011) conosciuto è proprio un numero di Mersenne formato (in base 10) da circa 12,9 milioni di cifre ed è stato scoperto nell’agosto del 2008:
243.112.609 − 1
Il numero 43.112.609 è primo, quindi rispetta la definizione di Mersenne.
Clicca qui per la top 10 dei primi dieci numeri primi conosciuti attualmente.