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:

• F₀ = 3
• F₁ = 5
• F₂ = 17
• F₃ = 257
• F₄ = 65.537

Eulero dimostrò che Fermat si sbagliava. Infatti il numero seguente non è primo:

F₅ = 4.294.967.297 = 641 · 6.700.417

Se F_n 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:

x² + 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 x² + 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:

M_n = 2ⁿ - 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 M₆₇ e M₂₅₇ (che non sono primi), mentre non comparivano M₆₁, M₈₉ e M₁₀₇ (che sono primi). Si può sostenere che:

• Se M_n è primo, allora anche n è primo. Invece n primo non garantisce che M_n sia primo.
• Se M_n 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:

2^43.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.