La successione del mese di Gennaio:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31,...


Per iniziare abbiamo scelto la successione piu' affascinante e misteriosa di tutte, la successione dei numeri primi. I numeri primi sono i mattoni con cui si costruiscono tutti i numeri interi (positivi), per esempio:

6 210693 899185923328 212667
2
3
5
2
3
7
3
 
3
11
7
29
31
11
13
 
13
2
2
3
3
3
2
2
2
3
3
3
41
7
13
3
19

La definizione operativa di numero primo è la seguente: un numero intero positvo, diverso da 1, si dice primo se è divisibile solo per 1 e per se stesso. Alcune domande che sorgono spontane sono:
 Quanti sono i numeri primi?
                    Dove sono i numeri primi?
Come possiamo riconoscere i numeri primi?
Qual'è il più grande primo conosciuto?

Chiaramente questa è solo un minima parte delle domande che ci possiamo porre riguardo ai numeri primi. Se volete sapere la risposta ad una di queste domande o scoprire che magari la risposta e' ancora sconosciuta ma comunque vedere a quali altre domande sui numeri primi ci conduce cliccate sulla domanda stessa, buon divertimento.
Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate.
L. Euler (1707-183)


torna a inizio pagina, torna alla pagina del calendario di formulas, torna a www.formulas.it


Quanti sono i numeri primi?



Che i numeri primi siano infiniti era noto già ai greci e sicuramente ad altre civiltà dell'antichità. Nel corso dei secoli sono state date numerose dimostrazioni dell'esistenza di infiniti numeri primi ne riportiamo qui sotto alcune:

Euclide


La più antica dimostrazione pervenutaci è quella di Euclide, il quale dimostra il seguente risultato:
Data una quantita' arbitraria di numeri primi esiste un numero primo diverso da essi.

La dimostrazione di Euclide è semplice ed elegante:
sia N il prodotto di tutti i numeri primi dati, allora il numero N+1 non è divisibile per nessuno dei numeri primi dati. Quindi i primi che dividono N+1 (o N+1 stesso in caso sia primo) sono primi diversi da quelli dati.

E. Kummer


Un' altra elegante dimostrazione dell'esistenza di infiniti numeri primi fu data dal matematico tedesco E. Kummer nel 1878, il suo enunciato è il seguente:
Esistono infiniti numeri primi.

Supponiamo che esista solo un numero finito di numeri primi. Allora detto N il prodotto di tutti i numeri primi, si ha esiste un numero primo p che divide sia N che N-1 (visto che N-1 è prodotto di numeri primi). Ma allora p divide anche N-(N-1)=1, ma ciò è assurdo.

C. Hermite


Probabilmente la dimostrazione più elegante di tutte (perchè i matematici la ritengono la più elegante secondo voi?) è quella pubblicata dal matematico H. Brocard nel 1915 ed attribuita ad C. Hermite:
Comunque scelto un numero intero N esiste un primo p maggiore di N.

Sia M il prodotto di N con tutti i numeri più piccoli di esso, cioè M=N·(N-1)· · 2· 1.
Per come abbiamo costruito M nessun numero primo minore di N può dividere M+1.
Dunque deve esistere un numero primo strettamente maggiore di N


Una volta assodata l'infintà dei numeri primi ci si puòchiedere se i numeri primi di una certa forma sono anche infiniti, per esempio: esistono infiniti primi della forma 4k+1? oppure della forma 5k+2?
La risposta la trovate qui a fianco. Un altra domanda che ha una lunga storia è la seguente: esistono infinte coppie di primi della forma (p, p+2)? numeri primi della forma (p, p+2) sono detti primi gemelli. A questa domanda a tutt'oggi non siamo in grado di rispondere anche se la stragrande maggioranza dei teorici dei numeri ritiene che i primi gemelli siano infiniti.
Teorema di Dirichlet (1837)
Se a e b sono due numeri privi di fattori primi in comune, allora esistono infiniti numeri primi della forma ak+b.



torna ad inizio pagina, torna alla pagina del calendario di formulas, torna a www.formulas.it




Dove sono i numeri primi?



Come abbiamo appena visto i numeri primi sono infiniti ma come sono distribuiti? se guardiamo l'immagine qui sotto vediamo che non c'è nessuna regolarità nella collocazione dei numeri primi, in effetti questo è uno dei fenomeni più affascinante e misteriosi della matematica. Per misurare la distribuzione dei numeri primi introduciamo una funzione contatore:

π (x)= numero dei primi minori di x
per esempio
π(10)= 4, π(100)= 25, π(1000)= 168, π(10000)= 1229, π(100000)= 9592 π(1000000)= 78498, π(10000000)= 664579,

appare evidente quindi che i primi si diradano crescendo, ma quanto si diradano? la quantità π(x)/x misura la densità dei primi nell'intervallo [1,x]
x π(x)/x
10 0.40
100 0.25
1000 0.17
10000 0.12
100000 0.10
1000000 0.08
10000000 0.07
Quindi per capire come e quanto si diradano i numeri primi bisogna trovare un buona stima per la funzione π(x)/x. Il primo a congetturare un possibile andamento per π(x)/x fu Adrien Marie Legendre (1752-1833), il quale propose:
π(x)/x ≈ log x
nel senso che il rapporto tra le funzioni π(x)/x e log x tende a 1 al cresecere di x . Questa stima fu dimostrata nel 1896 (indipendentemente) da Jacques Hadamard (1865-1963) e de la Vallé e Poussin (1866-1962) ed è il famoso Teorema dei numeri primi. Un formulazione alternativa della stima per π(x)/x è la seguente: la probabilità che il numero n sia primo è1/log n . La dimostrazione del Teorema dei numeri primi e gli sviluppi seguenti della teoria sono basati sul fondamentale e rivoluzionario lavoro di Bernard Riemann (1826-1866) Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse. (Sul numero dei numeri primi minori di una data quantità) (nella pagina web a cui rimanda il collegamento qui accanto trovate anche un traduzione in inglese), dove la teoria dei numeri viene collegata all'analisi complessa. In particolare Riemann lega la distrubuzione dei numeri primi alle proprietà degli zeri di una funzione di variabile complessa: la funzione zeta di Riemann.

   
Per essere precisi formula scritta qui accanto vale solo se la parte reale di s è strettamente maggiore di 1 (ogni numero complesso s si scrive come s=x+iy dove x e y sono numeri reali e i è l'unità immaginaria e sono detti rispettivamente la parte reale e la parte immaginaria di s) ma può essere conitinuatà analiticamente su tutto il piano complesso (tranne s=1)
La connessione risulta fra numeri primi e funzione zeta di Riemann risulta,
almeno intuitivamente, più evidente se consideriamo
lo sviluppo in prodotto di Eulero della funzione zeta stessa:
   
L. Eulero aveva, alla metà del 1700, ottenuto questa decomposizione ma solo per esponenti interi, da qui il nome prodotto di Eulero.




Un passo fondamentale nella dimostrazione del Teorema dei numeri primi è la verifica che la funzione zeta di Riemann non si annulli mai per numeri complessi con parte reale uguale ad 1. Viene naturale pensare che ottenendo ulteriori informazioni sul posizionamento degli zeri della funzione zeta di Riemann si possano dedurre informazioni più dettagliate sulla distibuzione dei primi. Ma dove sono gli zeri della funzione zeta di Riemann? Per visualizzare meglio la situazione potete il guardare il video realizzato da Gian Marco Todesco.
Nella didascalia viene riportata la descrizione del video fatta da Gian Marco Todesco stesso per YouTube.
Plot 3D della funzione zeta di Riemann. L'altezza è il logaritmo del modulo, il colore codifica l'argomento. Il picco al centro è il polo della funzione a s=1. I "buchi" sono gli zeri. Animazione creata con POV-Ray ( http://www.povray.org ). Computo dei dati effetuato con un programma apposito in C++ collegato con la biblioteca di Pari ( http://pari.math.u-bordeaux.fr/).

Si può verificare abbastanza facilmente che ζ(s) si annulla per tutti gli interi negativi pari, questi sono chiamti gli zeri banali della funzione ζ, ma tutti gli altri zeri dove sono? La celebrata ipotesi di Riemann asserisce:

Ipotesi di Riemann
Gli zeri non banali della funzione ζ(s) hanno tutti parte reale uguale ad 1/2.

A tutt'oggi non sappiamo se l'ipotesi di Riemann sia vera oppure o no, la maggioranza dei matematici ritiene che lo sia. Il Clay mathematical Institute offre un premio di un milione di dollari per la sua dimostrazione. All' inizio del 1900 Von Koch ha dimostrato che l'ipotesi di Riemann implica una stima molto più precisa per l'andamento asintotico di π(x)/x. Ma questa non è l'unica conseguenza dell'ipotesi di Riemann infatti nel corso degli anni moltissimi matematici hanno preso come base di partenza per le loro investigazioni la veridicità dell'ipotesi di Riemann, la scoperta della sua falsità provocherebbe un terremoto nel mondo matematico. Per fortuna anche tutti i riscontri pratici sono buoni, infatti è stato verificato che i primi 10 trillioni di zeri della funzione ζ hanno tutti parte reale uguale ad 1/2.

torna all'inizio, torna alla pagina del calendario di formulas, torna a www.formulas.it




Come possiamo riconoscere i numeri primi?



Il problema di come riconoscere un numero primo, o più in generale di avere un lista di tutti i numeri primi piu' piccoli di un dato valore, è un problema antico. A livello teorico il problema non sussiste, ma, praticamente, se abbiamo un numero con molte cifre (per esempio 100 cifre) come facciamo a verificare la sua primalità? Il metodo piu' antico, ed anche il più ovvio, e quello della "trial division" e cioèdi provare a dividere il numero di cui si vuole testare la primalità. Ma quali e quanti numeri dobbiamo provare: chiaramente ci basta provare a dividere per numeri primi ed inoltre ci basta provare con numeri primi piùpiccoli della radice quadrata del numero di cui vogliamo verificare la primalità. Facciamo un esempio pratico: supponiamo di voler verificare se 105481 èun numero primo. Poiché la radice quadrata di 105481 è compresa tra 324 e 325, dobbiamo provare a dividere 105481 per tutti i primi minori di 324. Ma quali sono i primi minori di 324? Il metodo più antico per determinare tutti i primi piùpiccoli di una data quantità è il crivello di Eratostene. Il funzionamento del crivello di Eratostene èmolto semplice: per iniziare scriviamo tutti i numeri da 2 a 324 in una tabella, dopo di che si cancellano i multipli di 2, poi quelli di 3 (perché è il primo numero non cancellato che incontriamo) e cosi via (nella tabella accanto abbiamo colorato invece di cancellare). Ogni volta che si finiscono di cancellare i multipli di un numero si passa la primo numero non cancellato che si incontra, e se ne eliminano i multipli (notate che questo numero risulta essere un numero primo per costruzione). Quando ci fermiamo? Ci fermiamo quando abbiamo cancellato i multipli di 17 visto che la radice quadrata di 324 è 18. I numeri che non sono stati cancellati (o nel caso della tabella a fianco che non sono stati colorati) sono primi (nella tabella a fianco i primi fino a 17 sono stati colorati per semplificare la lettura), ci rimane quindi da provare a dividere 105481 per tutti questi numeri primi..... buon divertimento.

Il Crivello di Eratostene

234 567 8910 111213 141516 1718
192021 222324 252627 282930 313233 3435
363738 394041 424344 454647 484950 5152
535455 565758 596061 626364 656667 6869
707172 737475 767778 798081 828384 8586
878889 909192 939495 96979899100101 102103
104105 106107108 109110111 112113114 115116117 118119120
121122 123124125 126127128 129130131 132133134 135136137
138139 140141142 143144145 146147148 149150151 152153154
155156 157158159 160161162 163164165 166167168 169170171
172173 174175176 177178179 180181182 183184185 186187188
189190 191192193 194195196 197198199 200201202 203204205
206207 208209210 211212213 214215216 217218219 220221222
223224 225226227 228229230 231232233 234235236 237238239
240241 242243244 245246247 248249250 251252253 254255256
257258 259260261 262263264 265266267 268269270 271272273
274275 276277278 279280281 282283284 285286287 288289290
291292 293294295 296297298 299300301 302303304 305306307
308309 310311312 313314315 316317318 319320321 322323324
Questo metodo, molto semplice da applicare, diventa però impraticabile quando il numero di cui vogliamo testare la primalità ha un numero significativo di cifre, diciamo a partire da 20 cifre. Infatti ci sono 450 milioni di primi minori di 1010 (e quindi primi di cui dovremmo cancellare i multipli per effetuare il crivello di Eratostene) e se anche cancellassimo tutti i multipi di un primo in un secondo ci vorrebero comunque, nella peggiore delle ipotesi, poco più di 14 anni per completare il procedimento, un pòtroppo per calcolare la primalitàdi un solo numero.
A partire dalla metà degli anni settanta sono stati elaborati svariati nuovi algoritmi per verificare la primalità di un numero. Alcuni di essi sono probalistici, nel senso che se il numero in questione passa il test allora vi è una data probabilitàche sia primo; altri deterministici (cioè se il numero passa il test allora è sicuramente primo). Senza entrare in dettagli tecnici èimportante ricordare che c'è una grossa differenza tra un algoritmo e il programma che realizza praticamente i passi dell'algoritmo, la cosidetta implementazione dell'algoritmo stesso. Per esempio a livello teorico (cioè a livello di algoritmi) il miglior test di primalità è quello recentemente elaborato nel 2002 da Manindra Agrawal, Neeraj Kayal, and Nitin Saxena (gli ultimi erano studenti dell'equivalente del nostro corso di laurea triennale nel 2002), che è l'unico algoritmo deterministico che termini in tempo polinomiale (ed infatti gli autori hanno ricevuto svariati premi per tale scoperta). Da un punto di vista pratico (cioè di algoritmi implementati) il test di primalitàche produce i migliori risultati (cioè riesce a determinare la primalità di numeri con il maggior numero di cifre) è un algoritmo probabilstico e precisamente l'algoritmo ECPP "Elliptic curve primality proving", che usa degli strumenti di geometria aritmetica in particolare alcune proprietà dei punti razionali dei tori (complessi) 1-dimensionali (eccone uno qui a fianco). Comunque anche con questi strumenti è impossibile, per il momento, determinare la primalità di numeri con più di 2500 cifre.

torna all'inizio, torna alla pagina del calendario di formulas, torna a www.formulas.it




Qual'è il più grande numero primo conosciuto?



Il più grande numero primo conosciuto è
243112609-1
ha quasi 13 milioni di cifre. Tanto per dare un idea di quanto sia grande pensate che se voleste scaricare in formato testo (ascii) questo numero vi trovereste davanti ad un file di 16,73 Megabytes (se volete provare eccolo qui), se lo volete stampare ci vogliono 3461 pagine con 50 righe per pagina e 75 cifre per riga. Nelle tabella qui sotto riportiamo i dieci più grandi primi conosciuti:

 primo numero di cifre
1243112609-1 12978189
2242643801-1 12837064
3237156667-1 11185272
3232582657-1 9808358
5230402457-1 9152052
6225964951-1 7816230
7224036583-1 7235733
8220996011-1 6320430
9213466917-1 4053946
1019249·213018586+1 3918990
Si nota immediatemente la quasi totale prevalenza di numeri della forma 2m-1. I numeri di questa forma sono chiamati numeri di Mersenne, in onore del matematico, filosofo, musicologo e teologo Marin Mersenne (1588-1648) il quale nella prefazione del suo libro Cogitata Physica-Mathematica (1644) affermò che: i numeri 2n-1 risultano primi per
n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 257 
e risultano essere composti per tutti gli altri valori di n. Questa affermazione di Mersenne è risultata falsa ma è bastata per far si che questi numeri ancor oggi si chiamino numeri di Mersenne. La lista di tutti i primi di Mersenne conosciuti la potete trovare qui. La ragione per cui tutti i piùgrandi primi sono primi di Marsenne è che per i numeri di questa forma ci sono test che possono essere compiuti "rapidamente" per verificare se siano primi o no. Per esempio si verifica immediatamente tramite l'identità
2ab-1=(2a-1)(1+2a+22a+… 2(b-1)a)
che 2m-1 può essere primo solo se m è primo. Non èvera l'implicazione inversa ci sono tantissimi numeri primi p per cui 2p-1 non èprimo, il più piccolo di tali primi è 11:
211-1=2047=23•89.

Come vengono trovati i primi di Mersenne? Il test per determinare se un numero Mersenne è primo è basato sul seguente teorema:
Lucas-Lehmer Test:  sia p un primo dispari, allora 2p-1 è primo se e soltanto se 2p-1 divide S(p-1) dove S(n+1) = S(n)2-2, e S(1) = 4.
Un test siffatto è molto facile da implementare su un calcolatore, ed infatti la maggior parte dei numeri primi di Mersenne che si conoscono sono stati scoperti grazie a svariate implementazioni del test nel periodo 1970-1990. George Woltman nel 1995 ebbe l'idea di creare un gruppo di lavoro virtuale e fondò il GIMPS (Great Internet Mersenne Primes Search), che è responsabile per la scoperta di 13 primi di Mersenne, ed in particolare dei 9 primi piùgrandi che si conoscano. GIMPS riunisce volontari da tutto il mondo e tutti possono partecipare e magari scoprire il prossimo primo di Mersenne. Il programma usa solo tempo macchina che altrimenti andrebbe perso (dovete solo registrarvi ed installare del software gratuito sul vostro computer). Per darvi un idea della lunghezza della verifica del test di Lucas-Lehmer pensate che per determinare che 242643801-1 è un numero primo sono durati 29 giorni su processore Intel Core2 a 3.0 GHz. Non è molto se pensate che fattorizzare numeri con più di sole diecimila cifre è al di là delle nostre attuali possibilità di calcolo.

torna all'inizio,
torna alla pagina del calendario di formulas,
torna a www.formulas.it
The theory of Numbers has always been regarded as one of the most obviously useless branches of Pure Mathematics. The accusation is one against which there is no valid defence; and it is never more just than when directed against the parts of the theory which are more particularly concerned with primes. A science is said to be useful if its development tends to accentuate the existing inequalities in the distribution of wealth, or more directly promotes the destruction of human life. The theory of prime numbers satisfies no such criteria. Those who pursue it will, if they are wise, make no attempt to justify their interest in a subject so trivial and so remote, and will console themselves with the thought that the greatest mathematicians of all ages have found in it a mysterious attraction impossible to resist.
G.H. Hardy (1877-1947)