Gyre e Gimble

a cura di Chiara Baldovino

Numeri Primi

Numeri Primi (Prime Numbers)

Un numero naturale n, con n>1, si dice primo se ammette come divisori solo n stesso e 1.

Esempi di numeri primi sono 2, 3, 5, 7, 11, 13, 17,19, 23, 29, 31.
L’importanza cruciale dei numeri primi è dovuta al Teorema Fondamentale dell’Aritmetica che afferma che ogni numero naturale maggiore di 1 si scrive come prodotto di uno o più numeri primi in modo unico a meno dell’ordine dei fattori. I numeri primi possono pertanto essere considerati come i mattoni dei numeri naturali.
Sebbene i matematici abbiano studiato  i numeri primi per più di venti secoli e molti risultati siano stati trovati e dimostrati, alcuni interessanti questioni rimangono irrisolte.
Quanti sono i numeri primi? Come si dividono? Quanti sono quelli più piccoli di mille, di un milione, di un miliardo, etc. ? Ci sono formule che permettono di ottenere detti numeri?
La dimostrazione dell’esistenza di un numero infinito di numeri primi, data da Euclide,  si trova nella Proposizione 20 del Libro IX  dei  suoi Elementi. Egli dimostra che esistono infiniti numeri primi, e cioè che la successione 2, 3, 5, 7, 11, 13, 17,19, 31, .... non ha fine.
Si supponga per assurdo che sia finita e che 2, 3, 5, 7, 11, 13, 17,19, 31, …, P  rappresenti la successione completa dei numeri primi con P massimo numero primo. Con queste ipotesi si consideri ora il numero Q così definito Q = (2·3·5·7·...·P)+1. È evidente che Q non è divisibile per nessuno dei numeri 2, 3, 5, 7, 11, 13, 17,19, 31, …, P  perchè il resto di questa divisione sarà sempre 1; ma se Q stesso non è numero primo allora è divisibile per qualche numero primo e perciò c’è un numero primo (che può essere lo stesso Q)  che supera  tutti quelli della successione. Questo però contraddice l’ipotesi che non esiste un numero primo maggiore di P  e perciò l’ipotesi è falsa.
Questa è una dimostrazione per reductio ad absurdum  e la reductio ad absurdum, tanto amata da Euclide, è una delle più belle armi del matematico.
Utilizzando questo  ragionamento si ha un metodo per determinare, almeno in teoria, una successione infinita di numeri primi. Partendo dal 2 e costruendo il successivo del prodotto dei primi numeri primi si ottiene o un nuovo numero primo oppure un numero composto che ha come fattore un primo diverso dai precedenti.

numeri primi

Si noti che per costruire l’n-esimo termine della successione (en) è necessario conoscere i primi n termini della successione formata dai primi numeri primi; pertanto questo è un metodo soltanto teorico per riuscire a generare un’infinità di numeri primi.                      
numeri primiFu Eratostene di Cirene, matematico e filosofo greco del II secolo a.C., a compilare, per primo,  tavole dei numeri primi. Egli scoprì una procedura per determinare i numeri primi minori di un dato n. Scritta per esteso l’intera sequenza dei numeri da 1 ad n, prendeva il numero primo più piccolo, cioè 2, e a partire da quello depennava tutti i suoi multipli (escluso il 2 stesso). Quindi passava al numero successivo che non era stato cancellato, ovvero 3, e cancellava tutti i suoi multipli. Continuava così, prendendo il numero successivo che non era stato ancora eliminato dall’elenco e depennando tutti i suoi multipli. In seguito il suo metodo fu battezzato “crivello (o setaccio) di Eratostene”.
Perfezionando questo metodo sono state calcolate tavole complete di numeri primi fino a circa 10.000.000; esse  ci forniscono una quantità enorme di dati empirici intorno alla distribuzione e alle proprietà dei numeri primi.
Sono  stati fatti numerosi tentativi per trovare formule aritmetiche e  algoritmi capaci di generare solo numeri primi, e sono state fatte numerose congetture sulla primalità dei numeri appartenenti a determinate classi; alcune di queste congetture sono state in seguito smentite, altre sono ancora da dimostrare.
Marin Mersenne (1588-1648), dilettante di matematica e amico di Pascal e Fermat, si ritagliava del tempo sottraendolo ai doveri monastici per dedicarsi alla ricerca di numeri primi.
Egli pensava che i numeri formati da certe “potenze  prime” di 2 diminuite di 1 fossero numeri primi e, nonostante  ciò contenesse qualche errore, Mersenne è passato alla storia per la sua lista e adesso un numero primo che si può scrivere nella forma Mp=2p-1 con p primo, è detto un numero primo  di Mersenne.
Perchè un numero di Mersenne sia primo deve esserlo lo stesso p, ma il fatto che p sia primo non garantisce che lo sia il numero di Mersenne corrispondente: infatti quando p assume i valori dei primi quattro numeri primi si generano primi di Mersenne

numeri primi

ma quando p è il quinto numero primo, cioè 11, il corrispondente numero di Mersenne si rivela composto: 211-1=2048-1=2047=23·89

marsenne
Marin Marsenne (Oizè 1588 - Parigi 1648)

Nel 1644 Mersenne affermò che per p =13, 17 e 19 i corrispondenti numeri di Mersenne erano primi e aveva ragione. In una lettera al matematico francese Frenicle de Bessy (1605-1675), Mersenne aveva affermato di conoscere tutti i numeri primi p minori o uguali a 257 per i quali  era primo ovvero p = 2, 3, 5, 7, 13, 17, 19 ,67, 127, 257 e tale dichiarazione aveva suscitato grande interesse poichè i numeri in questione erano così grandi che nessuno fu in grado di confermarla o refutarla.
Fu Eulero (1707-1783) a dimostrare nel 1750 che per p=31 si otteneva effettivamente un numero primo. Nel 1876 il matematico francese Edouart Lucas (1842-1891) stabilì che M127=2127-1 è primo e  ha 39 cifre ossia 170141183460469231731687303715884105727.
Mersenne però si era sbagliato due volte perchè anche M61, M89, M107 sono primi, mentre M67 e M257 non lo sono. La primalità di M67=267-1 non venne messa in discussione finchè nel 1903 Frank Nelson Cole (1861-1926) della Columbia University tenne ad un incontro della American Mathematical Society a New York una relazione intitolata Sulla fattorizzazione dei grandi numeri. Eric Temple Bell, che era tra il pubblico, ricorda l’episodio: “Cole, che fu sempre una persona di poche parole, si avvicinò alla lavagna e senza aprire bocca procedette al calcolo di elevamento di 2 alla sessantasettesima potenza; poi sottrasse accuratamente 1 ottenendo le spaventose 21 cifre di 147573952589676412927. Allora, senza una parola, passò a uno spazio libero della lavagna e, a mano, moltiplicò 193707721·761838257287. I due risultati coincidevano... Per la prima e fino ad allora unica volta  negli annali il pubblico applaudì vigorosamente l’autore di una comunicazione. Cole ritornò al suo posto senza dire una parola e nessuno gli pose domande”.
Dimostrare che M67=267-1 non è primo aveva richiesto a Cole “tre anni di domeniche”.
Si sarebbe invece dovuto attendere fino al 1952 per dimostrare, con l’uso dei  primi computer digitali, che 2257-1 non è primo mentre lo sono (2251-1) e (2607-1).
numeri primiIl cacciatore di numeri primi più influente dei tempi moderni è stato ispirato nella sua missione da alcuni timbri postali: quando era ragazzo, negli anni ’60,  il padre mostrò a George Woltman un timbro postale con l’espressione “211213-1 is prime” in cui compariva l’ultimo dei numeri primi trovati in quel periodo.
In seguito Woltman progettò software che diedero contributi fondamentali alla ricerca di numeri primi e nel 1996 fondò il GIMPS (Great Internet Mersenne Prime Search): esso utilizza la potenza di calcolo di computer di molti volontari (istituzioni accademiche, aziende e privati) in tutto il mondo che si servono di un programma ottimizzato per la verifica della primalità di un numero di Mersenne.
Il GIMPS è stato uno dei primi progetti di “calcolo distribuito” e uno di quelli di maggior successo perchè pochi mesi dopo che era stato messo on line un programmatore francese catturò il trentacinquesimo primo di Mersenne 21398269-1 e da allora ha rivelato altri 12 numeri primi di Mersenne con una media di circa uno all’anno:

  • nel Novembre del 1996, Joel Armengaud ha trovato 21398269-1;
  • il 24 Agosto del 1997, Gordon Spence ha trovato 22976221-1;
  • il 27 Gennaio del 1998, Roland Clarkson ha trovato 23021377-1;
  • il 1° Giugno del 1999, Nayan Hajratwala ha trovato 26975593-1;
  • il 14 Novembre 2001, Michael Cameron ha trovato 213466917-1.

Il record attuale del primo più grande è detenuto dal 45-esimo (in ordine di scoperta) primo di Mersenne 243112609-1 che è un numero di quasi 13 milioni di cifre ed è stato trovato nel 2008 da un computer dell’Università di California di Los Angeles connesso al GIMPS.
Fermat formulò la famosa ipotesi che tutti i  numeri della forma F(n)=22n+1 fossero primi. In effetti per n = 1, 2, 3, 4  si ottengono i seguenti numeri tutti primi:

numeri primi

Ma nel 1732 Eulero scoprì che F(5)=225+1=4294967297=641·6700417 e quindi è composto; successivamente si è trovato che altri di questi numeri di Fermat sono composti.
Un’altra notevole espressione che dà luogo a molti numeri primi è f(n)=n2-n+41 per n = 1,2, 3, ..., 40 risulta che  f(n) è primo, ma per n =41 non lo è. L’espressione n2-79n+1601 dà luogo a numeri primi per ogni n fino a 79, ma tale proprietà viene meno quando n = 80.
Il passo decisivo nella ricerca di una legge da cui dipenda la distribuzione dei numeri primi fu compiuto quando i matematici rinunciarono a cercare di prevedere la posizione precisa di un numero primo rispetto a quello precedente e a trovare una formula matematica semplice che rappresentasse tutti i numeri primi o desse il numero esatto dei numeri contenuti nei primi n numeri naturali e cercarono  di chiarire invece la distribuzione media dei primi tra i numeri naturali data dal rapporto numeri primi, dove numeri primiè il numero di primi compresi tra 1 ed N. L’importante passo che compì Gauss fu quello di tentare di capire se fosse possibile prevedere quanti fossero i numeri primi inferiori a 100, quanti quelli inferiori a 1000 e così via. Dato un numero N qualsiasi, c’era un modo per stimare quanti fossero i primi compresi tra 1 ed N?
Alla ricerca di una formula che gli permettesse di stimare tale numero Carl Friedrich Gauss iniziò a studiare le tavole dei numeri primi nel 1792 a 15 anni. Nel 1796 Lambert e von Vega pubblicarono una lista di tutti i primi fino a 400031. Il lavoro di Gauss avanzava lentamente perchè non accettava i valori pubblicati, ma insisteva per verificarli e infatti scriveva all’astronomo F. Encke: “Ho sfruttato spesso un quarto d’ora libero per setacciare un migliaio di numeri qua e là... Alla fine ho rinunciato del tutto senza nemmeno finire il primo milione.[..] Nel supplemento di Lambert il migliaio di numeri tra 101000 e 102000 è pieno zeppo di errori; nelle mie copie ho cancellato sette numeri primi e ne ho aggiunti due mancanti”.
Armato delle sue tavole dei numeri primi,  Gauss aveva ricavato le regolarità che questa tabella       (che contiene  molte più informazioni di quelle di cui Gauss disponeva) ci mostra:

numeri primi

Per N maggiore di 10000, l’incremento dei valori dell’ultima colonna è sempre pari a circa 2,3; perciò ogni volta che Gauss moltiplicava N per 10, doveva aggiungere 2,3 al rapporto tra N e i numeri primi. Questo collegamento tra moltiplicazione e addizione è precisamente la relazione racchiusa in un logaritmo e ciò che Gauss scoprì è che per contare i numeri primi si possono usare i logaritmi in base e: l’ultima colonna della tabella infatti poteva essere ricavata con buona approssimazione come il logaritmo in base e della prima colonna. La tabella che Gauss aveva costruito a 15 anni lo portò a formulare l’ipotesi che numeri primi e dunque egli poteva stimare che i numeri primi compresi fra 1 e N fossero circa numeri primi.

numeri primi
Jacques Solomon Hadamard (Versailles 1865 - Parigi 1963)

L’enunciato rigoroso del famoso Teorema sui numeri primi è il seguente: il numero di primi minori di un dato naturale N si avvicina asintoticamente al quoziente numeri primi quando N cresce indefinitamente:

numeri primi~numeri primi per numeri primi.

È una scoperta notevole perchè è sorprendente che due concetti matematici apparentemente lontani siano in realtà intimamente connessi.
Benchè  l’ipotesi di Gauss fosse semplice da enunciare, ai suoi tempi una dimostrazione rigorosa era molto al di là delle possibilità della scienza matematica e passarono circa cento anni prima che Hadamard (1896) a Parigi e Charles de la Vallèe Poussin  (1896) a Lovanio ne dessero una dimostrazione completa semplificata poi  da von Mangoldt e Landau. Ma molto prima di Hadamard il lavoro decisivo di preparazione era stato compiuto da Riemann (1826-66) in un famoso scritto in cui vennero tracciate le linee strategiche per l’attacco al teorema.

numeri primi
Atle Selberg (Langesund 1917 - Princeton 2007)

Successivamente Paul Erdös e Atle Selberg sbalordirono il mondo con una dimostrazione “elementare” ma  Selberg, pur avendo concordato precedentemente di pubblicare in coppia con Erdös, si accaparrò la maggior parte del merito e a lui solo fu assegnata nel 1950 la Fields Medal in larga misura per il lavoro sul Teorema dei numeri primi.

Vi sono però ancora molte altre ipotesi confermate da tutte le verifiche empiriche, ma di cui non si è ancora dimostrata la validità. Una di queste è la congettura di Goldbach (1690-1764) noto nella storia della matematica solo per questo problema. In una lettera ad Eulero nel 1742 egli osservava che ogni numero pari, tranne 2, poteva essere rappresentato come somma di due primi   (Es: 4= 2+2 ; 6= 1+5; 8=5+3;....) e chiedeva a Eulero una dimostrazione o un esempio che smentisse questo fatto; Eulero non diede mai risposte nè mai da allora ne è stata data una esauriente  anche se molti matematici a partire da Schnirelmann, e poi  Vinogradov, Hardy, Littlewood e Ramanujan si sono molto avvicinati.
Un altro problema invece riguarda il fatto che i numeri primi si presentano spesso in coppie della forma p, p+2 detti primi gemelli come 3 e 5 , 11 e 13, 29 e 31, 71 e 73,..., 100000000061 e 1000000000063; siritiene  corretta l’ipotesi che esistano infinite coppie così, ma non si è compiuto il minimo passo verso una dimostrazione.