Numero primo
In matematica, un numero primo (in breve anche primo) è un numero naturale maggiore di uno che sia divisibile solamente per uno e per sé stesso; al contrario, un numero maggiore di 1 che ha più di due divisori è detto composto. Ad esempio, 2, 3 e 5 sono primi, mentre 4 e 6 non lo sono perché sono divisibili rispettivamente anche per 2 e per 2 e 3. L'unico numero primo pari è 2, poiché tutti gli altri numeri pari sono divisibili anche per 2.

La successione dei numeri primi inizia con 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 ... (EN) Sequenza A000040, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation..
I numeri primi sono uno dei concetti basilari della teoria dei numeri, la parte della matematica che studia i numeri interi: alla base di questa importanza vi è la possibilità di costruire con essi, attraverso la moltiplicazione, tutti gli altri numeri interi; inoltre tale fattorizzazione è unica. I primi sono inoltre infiniti, e molte ricerche sono state compiute per comprendere la loro distribuzione.
I primi sono stati studiati sin dall'antichità: i primi risultati risalgono infatti agli antichi Greci, e in particolare agli Elementi di Euclide, scritti attorno al 300 a.C.; nonostante questo, esistono ancora numerose congetture a riguardo che non sono state ancora dimostrate. Tra di esse, le più note sono l'ipotesi di Riemann, la congettura di Goldbach e la congettura dei primi gemelli, che ad oggi (giugno 2009), dopo oltre un secolo dalla loro formulazione, non sono ancora state dimostrate.
Trovano spazio inoltre anche in molti altri ambiti della matematica pura, come ad esempio l'algebra o la geometria; recentemente hanno assunto un'importanza cruciale anche nella matematica applicata, con particolare riferimento alla crittografia.
Storia
Non è noto quando si è formato il concetto di numero primo, tuttavia un segnale che fa supporre una qualche consapevolezza della diversità di tali numeri si ha con l'Osso d'Ishango, un reperto osseo datato al Paleolitico superiore, in cui compaiono dei segni rappresentanti i numeri primi compresi tra 10 e 20. Per trovare un altro segno di questa consapevolezza bisogna recarsi in Mesopotamia ed aspettare il secondo millennio a.C.; a tale periodo appartengono infatti alcune tavolette contenti le soluzioni di alcuni problemi aritmetici che, per essere svolti, richiedono una buona conoscenza della fattorizzazioni in primi.[1] Allo stesso millennio appartiene anche il papiro di Rhind (trascritto intorno al 1650 a.C.), che contiene alcune espansioni in frazioni egiziane dei numeri nella forma 2/n. A seconda che n sia primo o composto, queste espansioni hanno una forma differente; di conseguenza questo porta a pensare che gli Egizi avessero qualche conoscenza sui numeri primi che non è giunta fino a noi.
La prima traccia incontestabile di un vero studio dei numeri primi è costituita dagli Elementi di Euclide, un libro composto tra il IV e il III secolo a.C., che fornisce un quadro completo delle conoscenze matematiche del tempo. Quest'opera contiene alcuni risultati fondamentali, tra cui il teorema dell'infinità dei primi,[2] e il lemma di Euclide,[3] che prova un'importante caratterizzazione dei numeri primi.[4] Euclide dimostra anche la possibilità di fattorizzare ogni intero positivo come prodotto di primi.[5] All'antica Grecia dobbiamo anche il crivello di Eratostene, un semplice algoritmo per determinare quali sono i numeri primi.[6]
I secoli seguenti registrarono un certo disinteresse per lo studio dei numeri primi[7] e per diverso tempo non furono provati risultati di particolare rilevanza su questo argomento. L'interesse per i numeri primi riprese vigore nel diciassettesimo secolo, con le dimostrazioni di nuovi e importanti risultati sui primi. Alcuni di questi sono dovuti a Pierre de Fermat: in particolare egli provò un teorema sulle congruenze modulo un primo, noto come "piccolo teorema di Fermat", e il teorema sulle somme di due quadrati che afferma che tutti i primi di una certa forma si possono scrivere come somma di due quadrati. Congetturò inoltre che tutti i numeri nella forma 22n + 1 (oggi chiamati in suo onore numeri di Fermat) fossero primi; Fermat stesso aveva verificato la sua congettura fino ad n=4; tuttavia Eulero mostrò che per n=5 si otteneva un numero composto e ad oggi non sono noti altri numeri di questo tipo che siano primi. Nello stesso periodo, il monaco francese Marin Mersenne pose l'attenzione sui primi nella forma 2p - 1, con p primo, che oggi sono chiamati in suo onore primi di Mersenne.
Altri risultati vennero ottenuti da Eulero nel corso del diciottesimo secolo, tra cui la divergenza della serie infinita 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ..., in cui gli addendi sono gli inversi dei un numeri primi, e il cosiddetto prodotto di Eulero, una formula che evidenzia il legame dei primi con la serie armonica.[8] Nella corrispondenza di Eulero con Christian Goldbach, quest'ultimo formulò inoltre la famosa congettura di Goldbach, ancora oggi non dimostrata, che riguarda la rappresentazione dei numeri naturali pari come somma di numeri primi.
Dalla fine del Settecento, l'attenzione di molti matematici si rivolse allo studio della distribuzione asintotica dei primi, ossia allo studio dell'andamento della funzione che conta i primi minori o uguali ad x. Legendre e Gauss congetturarono indipendentemente che tale funzione tende, al crescere di x, a x / ln(x), dove ln(x) indica il logaritmo naturale di x.[9] Nel 1859 Bernhard Riemann collegò questa problema con il posizionamento degli zeri della funzione zeta di Riemann; questo approccio portò alla dimostrazione della congettura, compiuta in modo indipendente da Hadamard e de la Vallée Poussin nel 1896. Tale risultato è oggi noto col nome di teorema dei numeri primi.
I numeri primi restarono confinati nell'ambito della matematica pura fino agli anni Settanta, quando venne sviluppato il concetto di crittografia a chiave pubblica; il primo algoritmo di questo tipo, l'RSA, sfrutta infatti la difficoltà di fattorizzare numeri grandi formati da due soli fattori primi. Per questo motivo, ha assunto una notevole importanza anche la ricerca di numeri primi sempre più grandi. A partire dal 1951, tale ricerca viene effettuata attraverso l'uso di computer.
Prime proprietà
Il più piccolo numero primo è 2; tutti gli altri sono dispari, in quanto ogni numero pari è divisibile per 2. Nel passato 1 era a volte considerato un numero primo: ad esempio Derrick Norman Lehmer lo incluse nella sua tavola dei numeri primi pubblicata nel 1914.[10] Oggi tuttavia si preferisce escluderlo, in quanto il suo inserimento tra i primi costringerebbe a riformulare in maniera più complessa diversi teoremi (come il teorema fondamentale dell'aritmetica) per tenere conto di questo caso speciale.
Un metodo, che discende direttamente dalla definizione, per verificare se un numero n è primo è controllare che non sia diviso dai numeri primi minori di n. Ad esempio, per provare che 11 è primo, basta osservare che non è diviso da 2, 3, 5 e 7 (che sono i primi minori di 11). Il crivello di Eratostene è un algoritmo per generare i numeri primi che si basa su tale metodo. Più precisamente, per determinare i primi nell'insieme dei numeri minori o uguali ad X, basta togliere dall'insieme tutti i multipli dei primi minori di X (esclusi i primi stessi);[11] i numeri primi cercati saranno i numeri rimanenti al termine di queste esclusioni. In effetti, è possibile migliorare questo algoritmo fermandosi ad eliminare i multipli dei primi minori o uguali alla parte intera della radice di X: se infatti un numero composto c ha tutti i fattori maggiori della radice di X, allora è maggiore di X, in quanto, dovendo avere almeno due fattori,
I numeri primi cercati saranno i numeri rimanenti al termine di queste esclusioni. La figura a destra mostra il funzionamento dell'algoritmo per X=120.
Il concetto di numero primo ammette inoltre una semplice interpretazione geometrica: i numeri n che non sono primi sono esattamente quei numeri che possono essere rappresentati come rettangoli composti da n quadratini i cui lati sono maggiori di 1.
Ad esempio 12 non è primo, perché può essere rappresentato come un rettangolo di lati 3 e 4, mentre 11 è primo, perché non ammette nessuna rappresentazione di questo tipo.
Scomposizione in fattori primi
L'importanza dei numeri primi in matematica è enorme e deriva essenzialmente dal teorema fondamentale dell'aritmetica, il quale asserisce che qualsiasi numero naturale diverso da uno può essere scomposto in fattori primi, e tale scomposizione è unica a meno dell'ordine dei fattori.
Ad esempio, 23244 si fattorizza come
e ogni altra sua fattorizzazione in numeri primi è ottenuta da questa permutando i fattori. Ad esempio, l'"ulteriore" fattorizzazione
non è altro che quella precedente con i fattori scritti in un ordine diverso. A causa di questa proprietà, ci si riferisce a volte ai numeri primi come agli "atomi dell'aritmetica".[12]
Questa è tra l'altro la ragione principale per cui 1 è escluso dall'insieme dei primi. Infatti, se si moltiplica una fattorizzazione di un numero per uno, un numero di volte a piacere, si ottiene sempre il numero di partenza, creando così fattorizzazioni distinte.
Una proprietà strettamente collegata alla fattorizzazione unica è il lemma di Euclide: se un primo p divide il prodotto ab, allora divide a o b. Questa è considerata la definizione stessa di elemento primo in un dominio d'integrità,[13] ed è ovvia a partire dal teorema fondamentale dell'aritmetica: la fattorizzazione di ab dovrà infatti contenere il primo p, e visto che p non può essere "spezzato" in due fattori, deve necessariamente essere nella fattorizzazione di almeno uno dei due numeri.
Infinità
I numeri primi sono infiniti. La più antica dimostrazione pervenutaci è quella di Euclide, che la presenta nel IX libro degli Elementi, come proposizione 20, con le parole:
La dimostrazione procede per assurdo. Supponendo infatti che esistano solo un numero finito di numeri primi , si può considerare il numero : questo numero è ovviamente maggiore di 1 e diverso da tutti i numeri primi . Ora, vi sono due possibilità per q: può essere primo o composto. Se fosse primo avremmo però una contraddizione, perché abbiamo assunto che i siano tutti i numeri primi; se fosse invece composto, dovrebbe avere una fattore primo d, che deve essere uno dei numeri primi . Ma allora d divide sia q che il prodotto (essendo uno dei numeri primi), e quindi deve dividere la loro differenza , il che è impossibile. Quindi q non può essere né primo né composto: ma questo è assurdo, e i numeri primi sono infiniti.
Una questione che sorge dalla dimostrazione è se i numeri nella forma , cioè il prodotto dei primi n primi più 1 (detti numeri di Euclide), siano o meno primi. Questo avviene nei primi casi (2·3+1=7 è primo, così come 2·3·5+1=31), ma è falso in generale: il più piccolo di tali numeri ad essere composto è
Non è noto se in questa successione esistano infiniti numeri primi, anche se è stato congetturato che sia così.[14]
Altre dimostrazioni sono state create nel corso dei secoli: Eulero dimostrò questo teorema a partire dalla divergenza della serie armonica, Goldbach attraverso i numeri di Fermat, mentre Harry Furstenberg ne ideò una usando metodi di topologia.[15]
Un teorema più forte, da cui si ricava facilmente l'infinità dei numeri primi, è quello che stabilisce che la serie 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ..., formata dalla somma degli inversi dei numeri primi, diverge,[16] ed in particolare, usando la notazione O-grande:
Questo teorema è dovuto a Eulero, che lo dimostrò nel diciottesimo secolo.
Dalla dimostrazione di Euclide segue anche che
Tale disuguaglianza può essere migliorata: H. Bonse dimostrò nel 1907 (disuguaglianza di Bonse) che[18]
per n > 3. Su questa strada, è stato dimostrato che la disuguaglianza
è verificata per ogni n > 2k.[19]
Distribuzione dei numeri primi
Una volta dimostrato che i numeri primi sono infiniti, sorge spontaneo chiedersi come si distribuiscono all'interno della sequenza dei numeri naturali, cioè quanto sono frequenti e quando ci si può aspettare di trovare l'n-esimo numero primo. Questo studio fu iniziato verso la fine del XVIII secolo indipendentemente da Gauss e da Legendre, che introdussero la funzione (detta funzione enumerativa dei primi) e congetturarono che essa fosse approssimativamente
Il tentativo di dimostrare questa congettura attraversò tutto l'Ottocento; i primi risultati furono ottenuti tra il 1848 e il 1859 da Chebyshev, che dimostrò usando metodi puramente aritmetici che esistevano due costanti A e B tali che
per x sufficientemente grande. Riuscì anche a provare che, se il limite del rapporto esiste, allora esso deve essere 1.
Una dimostrazione fu invece trovata nel 1896 da Hadamard e da de la Vallée-Poussin, che, pur lavorando indipendentemente l'uno dall'altro, usarono metodi simili, basati sull'uso della funzione zeta di Riemann, la quale era stata introdotta da Bernhard Riemann nel 1859. Per una dimostrazione che usasse soltanto metodi elementari (cioè senza usare metodi di analisi complessa) si dovette attendere invece fino al 1949, quando essa fu ideata da Selberg e Erdős. Il teorema è oggi noto come teorema dei numeri primi.
Gauss aveva introdotto anche una stima più precisa, utilizzando la funzione logaritmo integrale:
Nel 1899 de la Vallée-Poussin dimostrò che l'errore che si commette approssimando in questo modo è
per una costante positiva a e ogni intero m; tale risultato è stato leggermente migliorato nel corso degli anni.[21] Inoltre, nel 1901 von Koch mostrò che se l'ipotesi di Riemann è vera, allora si ha la stima molto più precisa:
Una forma equivalente al teorema dei numeri primi è che pn, l'n-esimo numero primo, è ben approssimato da n ln(n). In effetti, pn è strettamente maggiore di questo valore, come è stato dimostrato da J. Barkley Rosser nel 1938;[22] questa disuguaglianza è stata migliorata fino ad arrivare, nel 1995, a
per n ≥ 2.[23]
Intervalli tra i numeri primi
Legato alla distribuzione dei numeri primi è lo studio degli intervalli tra due primi consecutivi. Questo, a parte la coppia formata da 2 e 3, deve essere necessariamente maggiore o uguale a 2, perché tra due numeri consecutivi almeno uno è pari e quindi non primo. Se due numeri primi hanno come differenza 2, sono detti gemelli: ad eccezione della "tripletta" formata da 3, 5 e 7, i numeri primi gemelli si presentano a coppie, ed è semplice verificare che, tranne nel caso 3 e 5, il numero posto tra di loro è sempre un multiplo di 6. Le più piccole coppie di primi gemelli sono (3,5), (5,7), (11, 13), (17, 19) e (29, 31). È stato congetturato che esistano infinite coppie di numeri primi gemelli, sebbene nessuno sia ancora riuscito a dimostrarlo; un'estensione di questa idea è chiedersi se, dato un numero pari k, la differenza tra due primi consecutivi sia pari a k infinite volte. Quest'ultimo problema prende il nome di congettura di Polignac ed è anch'essa indimostrata.
È facile invece mostrare che questa differenza può essere grande a piacere: dato un intero N, ed indicando con N! il suo fattoriale (cioè il prodotto di tutti i numeri compresi tra 1 ed N), i numeri
sono tutti composti: infatti, se m è minore di N, allora (N+1)!+m è divisibile per m, e quindi non è primo. La sequenza, che comprende N numeri consecutivi, è quindi priva di numeri primi. Ad esempio, se N=5, questi valori corrispondono a
mentre il valore successivo, 6!+7=727, è primo.[24] Dal teorema dei numeri primi discende facilmente che l'intervallo atteso tra due numeri primi consecutivi ha lunghezza log(n). Tuttavia ci si aspetta che questi intervalli siano talvolta molto più grandi e talvolta molto più piccoli. Ad esempio, la congettura dei primi gemelli, dice esattamente che questo intervallo è il minimo possibile infinite volte. Seppure questa congettura sia ancora aperta, recentemente si sono fatti grossi passi avanti in questa direzione. Nel 2007 infatti Goldston, Pintz e Yildirim hanno provato che
restando comunque molto lontani dalla dimostrazione della congettura. Anche sul problema opposto, ossia quello sugli intervalli inusualmente lunghi, i risultati dimostrati sono nettamente inferiori a quelli comunemente ritenuti veri. Ci si aspetta infatti che
In questo caso, i migliori risultati provati sono
e
dovuti entrambi a Pintz.
Un altro risultato classico, seppur più debole di quelli appena riportati, è il postulato di Bertrand (dimostrato nel 1850 da Chebyshev), che afferma che, per ogni n, esiste sempre un primo tra n e 2n. Un'interessante conseguenza di questo risultato è che è che ; considerando inoltre che p1=2 si deduce facilmente che per ogni n vale la disuguaglianza
Nel corso dei secoli, sono state proposte molte congetture sugli intervalli tra primi consecutivi. Le più famose sono la congettura di Legendre, che afferma che tra due quadrati consecutivi vi è sempre un primo, la congettura di Brocard che asserisce che tra i quadrati di due primi dispari consecutivi esistono sempre quattro numeri primi, e la congettura di Andrica che ipotizza che
Queste congetture sono tutte molto più deboli di quanto ritenuto comunemente vero, ma sono tuttora indimostrate. I migliori risultati in questa direzione sono la dimostrazione che tra n2 e (n+1)2 giace sempre almeno un primo o un semiprimo, dovuta a Chen Jingrun,[27] e il risultato di Pintz riportato sopra.
Rapporti con gli altri campi della matematica
Essendo alle basi dell'aritmetica, i numeri primi sono ingredienti fondamentali in un gran numero di settori della matematica.
Funzioni aritmetiche
Le funzioni aritmetiche, ossia le funzione definite sugli interi e a valori nei numeri complessi, rivestono un ruolo cruciale nella teoria dei numeri. In modo particolare, tra queste le più importanti sono le funzioni moltiplicative, ovvero quelle funzioni f in cui, per ogni coppia (a,b) di numeri coprimi, si ha
Esempi di funzioni moltiplicative sono la funzione phi di Eulero, che ad n associa il numero degli interi che sono al contempo minori e coprimi con n, e le funzioni divisore e sigma, che ad n associano rispettivamente il numero dei suoi divisori e la loro somma. Il valore di tali funzioni nelle potenze dei primi è
Grazie alla proprietà che le definisce, le funzioni aritmetiche si possono facilmente calcolare conoscendo il valore che esse assumono nelle potenze dei primi. Infatti, dato un intero n di fattorizzazione
si ha che
e dunque si è ricondotto il problema di calcolare f(n) a quello di calcolare f sulle potenze dei primi che dividono n, valori che sono in genere più semplici da ricavare rispetto ad una formula generale. Ad esempio, per conoscere il valore della funzione phi di Eulero su n = 450 = 2×32×52 è sufficiente calcolare
Il fatto che una funzione moltiplicativa sia individuata dai valori assunti in corrispondenza delle potenze dei numeri primi è all'origine dell'uso delle serie di Bell, che sono delle particolari serie formali di potenze. Data una funzione moltiplicativa f e un primo p, la serie di Bell di f rispetto a p è:
In particolare, se f è completamente moltiplicativa (cioè se f(ab) = f(a) f(b) per ogni a e b), allora f è individuata dai valori di f(p), per p primo, e la sua serie di Bell è:
Numeri p-adici
Un altro degli argomenti principali della teoria dei numeri è costituito dallo studio dei numeri p-adici e delle loro proprietà. Tali numeri sono definiti nel modo seguente: per ogni primo p si considera una norma sui numeri razionali che, valutata su un numero razionale q, assume valori che si avvicinano allo 0 al crescere della massima potenza di p che divide q. Tale norma è detta "norma p-adica". Completando il campo dei numeri razionali rispetto alla metrica indotta da tale norma, si ottiene un campo, indicato con , che "estende" i numeri razionali in un modo diverso dai numeri reali. Gli elementi di tale campo sono detti numeri p-adici. Tali numeri si possono anche costruire come limite proiettivo degli anelli .
Teoria dei gruppi
I numeri primi hanno un ruolo centrale anche nell'algebra. Nella teoria dei gruppi, un gruppo in cui ogni elemento ha ordine la potenza di un primo p è detto p-gruppo. Se invece l'ordine di ogni elemento è solamente multiplo di p, il gruppo è detto primario. Se il gruppo è finito, questo avviene per tutti e soli i gruppi la cui cardinalità è la potenza di un primo; nel caso infinito, invece, per ogni primo p vi è un unico gruppo di tal tipo (a meno di isomorfismi): il p-gruppo di Prüfer.
È noto che i p-gruppi hanno un centro non banale, e di conseguenza non possono essere semplici (a parte il gruppo con p elementi); se il gruppo è finito, inoltre, tutti i sottogruppi normali intersecano il centro in modo non banale.
Tutti i gruppi con un numero primo di elementi sono ciclici e dunque abeliani; anche ogni gruppo di ordine p2 è abeliano. Inoltre, ogni gruppo abeliano finito è isomorfo al prodotto diretto di un numero finito di p-gruppi ciclici.
Il teorema di Cauchy afferma che, dato un gruppo di ordine n e un primo p che lo divide, esiste un elemento di ordine p, e quindi un sottogruppo con p elementi. Tale teorema è generalizzato dai teoremi di Sylow, che garantiscono che in ogni gruppo di ordine n esiste almeno un sottogruppo di ordine pm, per ogni pm che divide n.
Teoria degli anelli e teoria dei campi
Nella teoria degli anelli, la caratteristica di un dominio d'integrità D è 0 oppure un numero primo. Per un campo F, che è un particolare tipo di dominio di integrità, la caratteristica determina il sottocampo fondamentale di F: se essa è diversa da 0, e dunque è un numero primo, allora tale sottocampo è isomorfo al campo delle classi di resto .
Si mostra poi che tutti i campi finiti formano uno spazio vettoriale sul campo , e di conseguenza hanno un numero di elementi che è primo o è una potenza di un primo. Inoltre, due campi con lo stesso numero di elementi sono isomorfi; in particolare, ogni campo con un numero primo p di elementi coincide con , mentre ogni campo con pn elementi è un'estensione di Galois di un campo con p elementi.
Tra le estensioni dei numeri razionali, un ruolo importante è svolto dalle estensioni ciclotomiche, ossia da quei campi che si possono ottenere aggiungendo a le radici n-esime dell'unità, per un qualche numero naturale n. Il grado di queste estensioni è strettamente legato alla primalità di n. Infatti esso è n-1 se e solo se n è primo. Questo proprietà si dimostra essere equivalente al fatto che il polinomio
è irriducibile tra i polinomi a coefficienti razionali se e solo se n è primo. Per una dimostrazione si può procedere come segue: se n è composto (ad esempio n = ab, con a e b interi maggiori di 1), lo si può dividere in a gruppi di b addendi, arrivando ad una scomposizione. Ad esempio, se n=10, prendendo a = 2 e b = 5, P(x) si può scomporre come
Per dimostrare l'inverso, si può usare l'invece il criterio di Eisenstein. Grazie a questa proprietà risulta inoltre che se n è primo, allora questo polinomio coincide con l'n-esimo polinomio ciclotomico.
Aritmetica modulare
Anche nell'aritmetica modulare i numeri primi svolgono un ruolo molto importante: l'anello delle classi di resto è infatti un campo se e solo se n è primo. In questo caso lo studio delle classi di resto è più semplice del caso generale, e fornisce un'utile base di partenza per l'analisi delle classi di resto con n qualunque.
Anche l'esistenza di una radice primitiva dell'anello è legata ai numeri primi: questa infatti esiste solamente se n è un numero primo, 1, 2, 4 oppure un numero nella forma o , dove p è un primo dispari.[28]
Uno dei teoremi più importanti dell'aritmetica modulare è costituito dal piccolo teorema di Fermat. Tale teorema afferma che, per ogni primo p e ogni numero naturale a si ha
Equivalentemente, per ogni primo p e ogni intero a coprimo con p, si ha:
Questa proprietà può essere usata per verificare se un numero non è primo, infatti se n è tale che
per qualche intero a, allora n non può essere primo. Tuttavia questa proprietà non può essere usata per controllare se un numero è primo: esistono infatti alcuni numeri, detti numeri di Carmichael (il più piccolo dei quali è 561), che verificano questa proprietà per ogni a pur non essendo primi . Recentemente, nel 1994, William Robert Alford, Andrew Granville e Carl Pomerance hanno dimostrato che vi sono infiniti numeri di tale tipo.[29]
Polinomi e progressioni aritmetiche
È stato dimostrato da Legendre alla fine del Settecento[30] che nessun polinomio a coefficienti interi può assumere valori soltanto primi: infatti, se esistesse un polinomio P(n) di questo tipo, si avrebbe P(1) = p per qualche primo p e quindi P(1) ≡ 0 mod p. Ma P(1) ≡ P(1+kp) mod p per ogni intero k, e quindi P(1+kp) dovrebbe assumere infinite volte il valore p (perché i multipli di p non possono essere primi). Tuttavia questo è assurdo, perché nessun polinomio può assumere uno stesso valore un numero di volte maggiore del proprio grado.[31]
Alcuni polinomi sembrano assumere valori primi "più spesso" degli altri: ad esempio Eulero notò che il polinomio di secondo grado produce numeri primi per ogni valore di n compreso tra 0 e 39; tuttavia, sebbene circa un terzo dei valori che questa funzione assume nei primi 10 milioni siano primi,[32] non è stato ancora dimostrato che ne esistano infiniti. Più in generale, non c'è alcun polinomio in una sola variabile e di grado maggiore di uno di cui sia stato dimostrato che assume infiniti valori primi. Diversa è la situazione per i polinomi in due variabili: Dirichlet dimostrò che questo avviene per ogni forma quadratica (a patto che a, b e c siano coprimi e che la forma non sia il quadrato di un polinomio di primo grado),[33] mentre nel 1998 John Friedlander e Henryk Iwaniec lo provarono per il polinomio di quarto grado .[34]
A differenza di quanto accade per i polinomi di grado più alto, Dirichlet dimostrò nel 1837 che ogni polinomio di primo grado ax+b assume infiniti valori primi se e solo se a e b sono numeri naturali coprimi. Equivalentemente, ogni progressione aritmetica contiene infiniti numeri primi se e solo se la sua ragione e il suo primo valore sono coprimi. La prima dimostrazione di questo teorema, detto teorema di Dirichlet, viene considerata la nascita della teoria analitica dei numeri.[35]
È noto inoltre che, se n e k sono coprimi, il rapporto tra M e i primi minori di M che sono congrui a k modulo n tende a per M che tende all'infinito, ovvero i primi tendono a dividersi equamente tra le progressioni di ragione n che contengono più di un primo.[36]
Sebbene non esistano progressioni aritmetiche i cui valori siano soltanto numeri primi, nel 2004 è stato dimostrato che esistono progressioni che contengono un numero arbitrariamente grande di termini consecutivi che sono primi (teorema di Green-Tao).[37] Tale risultato è stato migliorato nel 2006 per includere anche le progressioni polinomiali; più precisamente è stato dimostrato che, dati e dei polinomi P1, ...,Pm a coefficienti interi, esistono infiniti interi a e m tali che a+P1(n), ..., a+Pm(n) sono contemporanemanente primi per 1 ≤ n ≤ m.[38]
Tali teoremi non sono tuttavia costruttivi, ovvero non permettono di determinare esplicitamente delle progressioni arbitrariamente lunghe. La più lunga sequenza di primi (attualmente conosciuta) che sono termini consecutivi di una progressione aritmetica è composta da 25 numeri.[39] È stato anche congetturato che esistano sequenze arbitrariamente lunghe di questo tipo tali che tra due termini della progressione non ci siano altri numeri primi. La più lunga sequenza di primi di questo tipo finora trovata comprende 10 termini.[40]
Una progressione aritmetica di interesse particolare per la teoria dei numeri primi è quella di ragione 4: si possono infatti separare i primi (a parte 2) in due gruppi, quelli nella forma 4k+1 e quelli nella forma 4k+3. Il teorema di Fermat sulle somme di due quadrati asserisce che i primi che possono essere scritti come somma di due quadrati sono tutti e soli quelli del primo gruppo. Un'importante riformulazione di questo teorema è che un primo è scomponibile nell'anello degli interi di Gauss se e solo se è della forma 4k+1.
Problemi additivi
Per la loro definizione, i numeri primi sono intrinsecamente legati all'operazione di moltiplicazione. Tuttavia, sono di grande interesse anche alcuni problemi riguardanti loro proprietà additive.
Il più famoso di questi è senza dubbio la congettura proposta da Christian Goldbach nel Settecento, che afferma che ogni numero pari maggiore di 2 può essere espresso come somma di due primi. La congettura è tuttora indimostrata, ma è facilmente verificabile per gli interi “piccoli”, come ad esempio
- 4 = 2 + 2
- 6 = 3 + 3
- 8 = 3 + 5
- 10 = 3 + 7 = 5 + 5
- 12 = 5 + 7
- 14 = 3 + 11 = 7 + 7,
e tramite l'uso di computer è stata controllata anche per tutti gli n minori di 1018.[41]
Alla congettura di Goldbach ne è legata un'altra, più debole ma anch'essa indimostrata, che afferma che ogni numero dispari è la somma di tre numeri primi.
Seppure entrambi i problemi sembrino lontani dall'essere risolti, dalla loro formulazione sono stati fatti molti passi avanti verso una loro dimostrazione. Il primo risultato importante in tale direzione è dovuto a Ivan Vinogradov, che nel 1939 dimostrò che la seconda congettura è vera per ogni numero abbastanza grande, mentre Olivier Ramaré ha provato nel 1995 che ogni intero pari è somma di al più sei numeri primi.[42] Due anni dopo, Deshouillers, Effinger, Te Riele e Zinoviev hanno evidenziato un sorprendente legame con l'ipotesi di Riemann generalizzata, provando che essa implica la congettura debole di Goldabach.[43]
Sono noti anche altri risultati, sebbene molto più deboli. Usando il postulato di Bertrand si può dimostrare che ogni intero maggiore di 6 può essere scritto come somma di primi distinti. Inoltre, se pn è l'n-esimo numero primo, allora almeno uno tra pn, pn-1 e pn+1 può essere scritto come
scegliendo opportunamente i segni "più" e "meno".
Problemi additivi sono considerati anche i già citati teorema di Green-Tao sulle progressioni aritmetiche e la congettura dei primi gemelli e la congettura di Levy che afferma che ogni intero dispari è la somma di un primo e di un semiprimo pari.
Principali problemi aperti
Molte congetture riguardanti i numeri primi non sono ancora state dimostrate. La più importante tra queste è senza dubbio l'ipotesi di Riemann, uno dei problemi aperti più importanti di tutta la matematica: era uno dei ventitré problemi di Hilbert, enunciati nel 1900, ed essendo ancora insoluto è stato riproposto fra i sette problemi per il millennio nel 2000. Nella sua formulazione originale, tale ipotesi riguarda il posizionamento degli zeri complessi della funzione zeta di Riemann, e quindi non è immediatamente chiaro il suo legame con i numeri primi; tuttavia è stato dimostrato che la verità dell'ipotesi di Riemann avrebbe come conseguenza un notevole miglioramento della comprensione della distribuzione asintotica dei numeri primi.
Altri due problemi aperti molto famosi sono le già citate congetture di Goldbach, dei primi gemelli e di Legendre.
Altre congetture riguardano l'esistenza o meno di infiniti numeri primi in una certa forma. Ad esempio si pensa che esistano infiniti numeri primi nelle sequenze n2+1(EN) Sequenza A002496, su On-Line Encyclopedia of Integer Sequences, The OEIS Foundation., 2n-1 (primi di Mersenne, OEIS:000043), n!+1 e n!-1 (primi fattoriali, sequenze OEIS:002981 e OEIS:117141), o che esistano infiniti primi nella successione di Fibonacci.[44] Si congettura invece che gli unici primi di Fermat, i numeri primi nella forma 22n+1 siano in corrispondenza di n=0, 1, 2, 3 e 4.
Formule per i numeri primi
Una formula per i numeri primi è un'espressione che genera solamente numeri primi. Non sono note formule chiuse (che cioè non fanno ricorso né a limiti né a serie né a sommatorie la cui lunghezza dipenda dal dato iniziale) per trovare tutti i numeri primi fino a n, o anche solo l'n-esimo primo; sono state invece trovate alcune formule che generano solo numeri primi, seppure fondamentalmente inutili dal punto di vista pratico. Un esempio è dato dal teorema di Mills che afferma che esiste una costante θ tale che
è sempre un numero primo. Tuttavia non si conosce nessuna formula chiusa per calcolare la costante di Mills: le approssimazioni attualmente utilizzate si basano sulla sequenza dei cosiddetti primi di Mills (i numeri primi generati tramite questa formula), che non possono essere ricavati rigorosamente, ma solamente in maniera probabilistica, assumendo per vera l'ipotesi di Riemann.[45]
A seguito della dimostrazione del teorema di Matijasevič, sono stati trovati vari polinomi i cui valori positivi sono sempre numeri primi. Matijasevič dimostrò l'esistenza di un polinomio di 37° grado in 24 incognite, ma senza esplicitarlo; in seguito alcuni di questi sono stati determinati, ma rimangono poco utili per la ricerca di nuovi primi perché hanno diverse variabili e un grado molto elevato, ed inoltre assumono spesso valori negativi.[46]
Altre formule si possono costruire attraverso il teorema di Wilson con l'uso della funzione parte intera, ma anche queste sono sostanzialmente inutilizzabili a causa della loro elevata complessità computazionale.
Aspetti computazionali
Test di primalità
Un test di primalità è un algoritmo che permette di stabilire se un dato numero è primo oppure no. Nella teoria della complessità computazionale, questo problema è a volte denotato come PRIMES, ed è stato dimostarto che appartiene alla classe di complessità P.[47]
Il più antico e semplice test di primalità è quello di "divisione per tentativi", che consiste nell'applicare direttamente la definizione di numero primo: si prova a dividere il numero N per tutti i numeri minori di N: se nessuno di questi lo divide, allora il numero è primo. Un semplice miglioramento di questo metodo si ottiene limitando i tentativi di divisione ai numeri primi minori di . Sebbene molto semplice da descrivere e da implementare su un calcolatore, tale metodo è poco usato nella pratica, perché richiede tempi di calcolo che aumentano esponenzialmente rispetto al numero delle cifre di N. Esso tuttavia fornisce anche i suoi fattori primi (ed è quindi un algoritmo di fattorizzazione): questo non succede nel caso di algoritmi più sofisticati, che riescono a stabilire se un numero non è primo anche non determinando alcun divisore non banale.
Altri algoritmi di primalità piuttosto semplici ma poco utili dal punto di vista pratico sono il test che si può ricavare dal crivello di Eratostene e i test di Fermat e di Wilson, che si basano rispettivamente sul piccolo teorema di Fermat e sul teorema di Wilson.
Diversi altri algoritmi sono stati sviluppati nel corso del tempo: alcuni di essi si applicano solo a classi particolari di numeri, come ad esempio i test di Lucas-Lehmer e di Proth, che si applicano solo ai numeri di Mersenne e di Proth rispettivamente. Altri, come il test di Miller-Rabin, sono probabilistici, ovvero danno una risposta certa solo se affermano che il numero non è primo, mentre se si ottiene come risultato che il numero è primo, allora c'è solo un'alta probabilità che il numero effettivamente lo sia. I numeri che passano uno di questi test, pur senza essere primi, sono detti "pseudoprimi". La classe più famosa di pseudoprimi è quella dei numeri di Carmichael, che verificano il piccolo teorema di Fermat pur essendo composti.
Tra i test di primalità di uso generale, il più usato attualmente è l'ECPP, basato sulle curve ellittiche; sebbene la sua complessità computazionale non sia nota, sperimentalmente si osserva che esso è un algoritmo polinomiale nel numero delle cifre di n.[48] Nel 2002, i tre matematici indiani Manindra Agrawal, Neeraj Kayal e Nitin Saxena hanno sviluppato l'algoritmo AKS, il primo test di primalità deterministico con complessità polinomiale, provando dunque che il problema di stabilire se un numero è primo o no sta nella classe di complessità P.[49]
Algoritmi di fattorizzazione
Un programma che ha lo scopo di individuare i fattori primi di un numero è detto algoritmo di fattorizzazione; gli algoritmi di questo tipo possono funzionare anche da test di primalità, ma sono quasi sempre più lenti da eseguire. Dopo il metodo di divisione per tentativi, i più antichi algoritmi di questo tipo sono il metodo di Fermat, che si basa sulle differenze tra il numero e dei quadrati, efficace in particolare quando N è il prodotto di due numeri primi vicini tra loro, e il metodo di Eulero, che si basa invece sulla rappresentazione di N come somma di due quadrati in due modi diversi.
Più recentemente, gli algoritmi per la fattorizzazione sono stati basati su una gran varietà di tecniche diverse, come le frazioni continue o le curve ellittiche, mentre altri, come ad esempio il crivello quadratico, sono basati su miglioramenti del metodo di Fermat. Altri, come il metodo rho di Pollard, sono probabilistici, e non offrono la garanzia che, dato un numero non primo, ne trovino i divisori.
Ad oggi il più veloce algoritmo deterministico di impiego generale, ovvero senza necessità di numeri in forma particolare, è il general number field sieve, che ha complessità esponenziale sul numero di cifre di N;[50] è stato proposto un algoritmo che ha tempo di esecuzione polinomiale nel numero di cifre di N (algoritmo di Shor), ma esso richiede di essere eseguito su un computer quantistico, la cui simulazione su un normale calcolatore richiede un tempo esponenziale.
Impiego nella crittografia
Proprio la difficoltà di fattorizzare grandi numeri ha portato allo sviluppo del primo metodo efficace di crittografia a chiave pubblica, l'RSA. In questo sistema crittografico, la persona che deve ricevere un messaggio cifrato genera una chiave formata da tre numeri: uno (n) è il prodotto di due numeri primi di grandi dimensioni (generalmente si usano numeri dell'ordine di 1050), mentre gli altri due (e ed f) verificano la relazione , dove è la funzione di Eulero. Uno tra questi ultimi due numeri deve essere tenuto segreto (e dunque prende il nome di chiave privata), mentre l'altro deve essere reso noto insieme al numero n (andando a formare la "chiave pubblica").
Dopo aver trasformato il messaggio in un numero m (secondo un codice stabilito in precedenza), la procedura di criptazione e decriptazione consiste nell'elevamento a potenza di m per il numero tra e ed f reso pubblico, prendendone poi il resto nella divisione per n; il piccolo teorema di Fermat garantisce che dopo quest'operazione si possa ritornare allo stesso numero di partenza conoscendo sia e che f.
Bisogna notare che è possibile, in teoria, ricavare la chiave privata dalle informazioni pubbliche: questo richiede la fattorizzazione del numero n, ed essendo questa un'operazione che richiede molto tempo di calcolo, la trasmissione del messaggio si può considerare sicura se i due primi scelti sono "sufficientemente" grandi.
Nel 1991 la RSA Laboratories (l'azienda che ha sfruttato commercialmente l'RSA) ha pubblicato una lista di semiprimi, offrendo dei premi in denaro per la fattorizzazione di alcuni di essi, con lo scopo di provare la sicurezza del metodo e di incoraggiare la ricerca in questo ambito: l'iniziativa è stata chiamata RSA Factoring Challenge. Nel corso degli anni, diversi di questi numeri sono stati fattorizzati, ma il concorso è terminato nel 2007.[51][52][53]
Numeri primi grandi
Già da molti secoli la ricerca di numeri primi "grandi" ha destato l'interesse dei matematici; tuttavia questa ricerca ha assunto una particolare importanza negli ultimi decenni, a causa del bisogno di tali numeri che caratterizza algoritmi quali l'RSA.
Il metodo più efficace per ottenere numeri primi grandi risale al diciassettesimo secolo, di tale secolo è infatti la congettura di Marin Mersenne, che affermava che sarebbe stato primo (quando n<257) solo per n uguale a 2, 3, 5, 7, 13, 19, 31, 67, 127 e 257.[54] La verifica della primalità di tali numeri era molto al di là delle possibilità dell'epoca, ed infatti soltanto nel Novecento si scoprì che la congettura era falsa e probabilmente fatta "alla cieca", in quanto Mersenne tralasciò tre casi (per n = 61, 89 e 107) e non si accorse che i numeri corrispondenti a n = 67 e n = 257 erano in realtà composti.
M127 (un numero di 39 cifre) fu dimostrato essere primo da Édouard Lucas nel 1876, e rimase il numero primo più grande conosciuto fino al 1951, quando usando un calcolatore elettronico fu trovato il primo 180·(2127-1)+1, di 79 cifre. Da allora tutti i successivi primi più grandi sono stati scoperti con l'aiuto del computer: dal 1952 (quando lo SWAC dimostrò che M521 è primo) al 1996 essi sono stati trovati da supercomputer, e furono tutti primi di Mersenne (trovati usando il test di Lucas-Lehmer, un algoritmo specifico per questi numeri) ad eccezione di 391581·2216193-1, che detenne il record tra il 1989 e il 1992.[55][56]
In seguito, i dodici nuovi numeri primi più grandi sono stati scoperti attraverso il GIMPS, un progetto di calcolo distribuito basato anch'esso sul test di Lucas-Lehmer. Il più grande numero primo confermato, scoperto nell'agosto del 2008, è 243.112.609-1, un numero di quasi tredici milioni di cifre.[57] I numeri primi noti più grandi sono numeri primi di Mersenne o altri numeri primi particolari, per i quali si dispone di un test molto efficiente in termini computazionali.
La Electronic Frontier Foundation ha offerto dei premi in denaro per la prima scoperta di numeri primi oltre un certo numero di cifre. I primi due di questi premi, di 50.000 e 100.000 dollari, sono stati assegnati nel 2000 e nel 2008 per il raggiungimento, rispettivamente, di un milione e di dieci milioni di cifre; il più alto premio attualmente in palio è di 250.000 dollari, per l'arrivo al miliardo di cifre.[58][59]
Generalizzazioni
Il concetto di numero primo viene esteso anche in altri campi della matematica.
Teoria degli anelli
La definizione di numero primo può essere estesa a qualunque dominio d'integrità; vi sono generalmente due modi di estendere la definizione, in generale non equivalenti fra loro:
- un elemento è irriducibile se è un elemento non invertibile che non può essere scritto come il prodotto di due elementi non invertibili;[60]
- un elemento è primo se non è invertibile e ogni volta che divide il prodotto , allora divide oppure .[61]
Nell'anello degli interi le due definizioni sono equivalenti, e più in generale sono equivalenti in tutti gli anelli a fattorizzazione unica.
Inoltre, dato un anello A, un ideale I di A è detto "primo" se per ogni coppia a,b di elementi di A tali che almeno uno tra a e b appartiene a I.
Questa definizione è molto vicina a quella degli ordinari numeri primi, tanto che nell'anello gli interi gli ideali primi non nulli sono esattamente (2), (3), (5)..., ovvero quelli generati dai numeri primi (e più in generale, ciò avviene in ogni dominio ad ideali principali). Lo studio degli ideali primi è un punto centrale nella geometria algebrica e nella teoria dei numeri algebrica. Un'importante analogia tra numeri primi e ideali primi è dato dal fatto che nei domini di Dedekind per gli ideali vale l'analogo del teorema fondamentale dell'aritmetica.[62]
Teoria dei gruppi
Nella teoria dei gruppi, i gruppi sporadici sono considerati l'equivalente dei numeri primi: si dimostra che ogni gruppo semplice finito può essere ciclico, alternato, uno dei 16 tipi di gruppi semplici finiti di Lie o uno dei 26 gruppi sporadici.
Teoria dei nodi
Alcuni nodi primi |
In teoria dei nodi, un nodo primo è un nodo non banale che non può essere "scomposto" in due nodi più piccoli. In maniera più precisa, è un nodo che non può essere scritto come somma connessa di due nodi non banali.
Nel 1949 Horst Schubert dimostrò un teorema di fattorizzazione analogo al teorema fondamentale dell'aritmetica, che asserisce che ogni nodo è ottenibile in modo unico come somma connessa di alcuni nodi primi.[63] Per questo motivo, i nodi primi hanno un ruolo centrale nella teoria dei nodi: una loro classificazione è stato da sempre il tema centrale della teoria fin dalla fine del XIX secolo.
Numeri primi in natura
Molti numeri compaiono in natura, e quindi è inevitabile che alcuni di essi siano primi. Ci sono tuttavia relativamente pochi esempi di numeri che appaiono in natura perché sono primi: ad esempio, la maggior parte delle stelle marine hanno 5 braccia, e 5 è un numero primo; tuttavia non è stato trovato alcun motivo evidente per supporre che questo numero di braccia sia in qualche modo legato alla primalità di 5.[64] Il motivo per cui la maggior parte delle stelle marine, così come molti altri echinodermi, hanno una simmetria a 5 braccia rimane un mistero.
In entomologia si trova uno dei casi in cui si suppone che un numero compare proprio perché è primo. È stato infatti notato che alcune specie di cicale del genere Magicicada,[65] che trascorrono la maggior parte delle loro vite come larve, emergono come pupe solo a intervalli di 13 o 17 anni, dopo i quali si riproducono e muoiono dopo poche settimane. Si pensa che il motivo per cui l'intervallo di tempo sia un numero primo di anni è la difficoltà per un predatore di evolversi specializzandosi come predatori delle Magicicada:[66] se infatti questi insetti apparissero dopo un numero non primo di anni, allora tutti i predatori il cui ciclo vitale è un divisore di quel numero sarebbero sicuri di trovare le Magicicada. Se i periodi di questi insetti fossero invece di 14 o 15 anni si stima che dopo due secoli ci sarebbe una popolazione di predatori del 2% più alta.[67] Sebbene esile, questo vantaggio evolutivo sembra essere stato sufficiente a selezionare cicale il cui periodo è 13 o 17 anni.
Numeri primi nell'arte e nella letteratura
I numeri primi hanno influenzato molti artisti e scrittori. Il compositore francese Olivier Messiaen era ossessionato da tali numeri [68] e li utilizzò per creare musica non metrica: in opere come La Nativité du Seigneur (1935) o Quatre études de rythme (1949-50) impiegò simultaneamente motivi la cui lunghezza è un numero primo per creare ritmi imprevedibili. Secondo Messiaen questo modo di comporre era "ispirato dai movimenti dalla natura, movimenti di durate libere e disuguali".[69] Anche nel movimento di apertura di un'altra composizione, Quatuor pour la fin du temps, Messiaen utilizzò i numeri primi. Con l'obbiettivo di dare l'idea dell'eternità, accostò infatti un tema di 17 note ad un tema di 29 note. Essendo primi entrambi i numeri, i temi si ripetono insieme solo dopo 17·29=493 note. La stessa idea è stata utilizzata da Jem Finer che ha ideato un'installazione sonora che sino al 31 dicembre 2999 suonerà motivi sempre diversi.[68]
I numeri primi svolgono un ruolo anche in alcuni libri. Ad esempio, nel romanzo di fantascienza Contact di Carl Sagan (così come nella sua versione cinematografica), i numeri primi vengono utilizzati dagli alieni per comunicare; un caso reale di uso dei primi come mezzo di comunicazione è presente nel saggio L'uomo che scambiò sua moglie per un cappello, del neurologo Oliver Sacks, dove sono descritti due gemelli autistici che per parlarsi si scambiano primi molto elevati. Vi sono riferimenti ai numeri primi anche nel romanzo di Mark Haddon Lo strano caso del cane ucciso a mezzanotte, in cui la numerazione dei capitoli segue la successione dei primi, e nel romanzo di Paolo Giordano La solitudine dei numeri primi, vincitore del premio Strega nel 2008.
Molti film riflettono la fascinazione popolare verso i misteri dei numeri primi e della crittografia, come ad esempio Cube - Il cubo, I signori della truffa, L'amore ha due facce e A beautiful mind.
Note
- ^ Otto Neugebauer, Capitolo 2, in Le scienze esatte nell'antichità, Milano, Feltrinelli, 1974, ISBN 8807222817.
- ^ Libro IX, Proposizione 20.
- ^ Libro VII, Proposizione 30.
- ^ Questa proprietà verrà usata per generalizzare la definizione di numero primo agli anelli.
- ^ Libro VII, Proposizioni 31 e 32. Il primo a dimostrare esplicitamente che tale fattorizzazione è unica (cioè a dimostrare il teorema fondamentale dell'aritmetica nella sua completezza) fu Gauss nelle Disquisitiones Arithmeticae.
- ^ Per quanto semplice, tale algoritmo è troppo costoso dal punto di vista computazionale e quindi non è generalmente usato nelle applicazioni pratiche.
- ^ (EN) Prime numbers, su www-history.mcs.st-andrews.ac.uk. URL consultato il 23 febbraio 2009.
- ^ Du Sautoy, L'enigma dei numeri primi, p. 149.
- ^ Du Sautoy, op. cit., capitolo 2.
- ^ Conway e Guy, Il libro dei numeri, p. 111.
- ^ Si noti che se si considera che 1 sia primo anche il crivello di Eratostene andrebbe leggermente modificato, infatti se si cominciasse con l'eliminare tutti i multipli di 1 si sarebbe costretti ad eliminare qualsiasi altro numero.
- ^ Ad esempio in du Sautoy, L'enigma dei numeri primi.
- ^ vedi il paragrafo sulle generalizzazioni.
- ^ (EN) Eric W. Weisstein, Euclid Number, su mathworld.wolfram.com. URL consultato il 23 febbraio 2009.
- ^ (EN) Furstenberg, Harry, On the infinitude of primes, in Amer. Math. Monthly, vol. 62, n. 5, 1955, p. 353, DOI:10.2307/2307043.
- ^ Vedi la dimostrazione.
- ^ Vedi ad esempio in Moser, An Introduction to the Theory of Numbers, p. 24.
- ^ H. Bonse, "Üer eine bekannte Eigenschaft der Zahl 30 und ihre Verallgemeinerung", in Arch. Math. Phys, vol. 12, 1907, pp. 292-295.
- ^ L. Panaitopol, "An inequality involving prime numbers", in Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat., vol. 11, 2000, pp. 3-35.
- ^ Con questa espressione si intende che il limite del rapporto tra queste due espressioni tende a 1 quando x tende a infinito.
- ^ Ingham, op. cit., p. xi.
- ^ J. B. Rosser, "The nth Prime is Greater than n ln n", in Proceedings of the London Mathematical Society, vol. 45, 1938, pp. 21-44.
- ^ P. Dusart, "The k^(th) Prime is Greater than k(lnk+lnlnk-1) for k>=2.", in Math. Comput, vol. 68, 1999, pp. 411-415.
- ^ Si noti tuttavia che in generale non è vero che il numero successivo è primo, ad esempio se n è dispari, allora N!+(N+1) è divisibile per 2.
- ^ D.A. Goldston, J. Pintz, Y. Yilidrim, "Primes in tuples. II." (PDF), in Acta. Math., to appear.
- ^ a b c Template:Citaweb
- ^ J. R. Chen, "On the Distribution of Almost Primes in an Interval.", in Sci. Sinica, vol. 18, 1975, pp. 611-627.
- ^ Apostol, op. cit., capitolo 10.
- ^ W. R. Alford, A. Granville e C. Pomerance, "There are Infinitely Many Carmichael Numbers.", in Annals of Mathematics, vol. 139, 1994, pp. 703-722.
- ^ Boyer, Storia della matematica, p. 565.
- ^ Harold Stark, An introduction to number theory, 10ª ed., Cambridge, The MIT Press, 1998, ISBN 0-262-69060-8.
- ^ Devlin, Dove va la matematica, p. 73.
- ^ Harold Davenport, Aritmetica superiore, p. 33.
- ^ (EN) John Friedlander e Henryk Iwaniec, The polynomial X2 + Y4 captures its primes (PDF), in Annals of Mathematics, vol. 148, 1998, pp. 945–1040, DOI:10.2307/121034.
- ^ Apostol, Introduction to Analytic Number Theory, p. 7.
- ^ Apostol, Introduction to Analytic Number Theory, p. 149.
- ^ Ben Green e Terence Tao, The primes contain arbitrarily long arithmetic progressions (PDF), in Annals of Mathematics, vol. 167, 2008, pp. 481-547. URL consultato il 23 febbraio 2009.
- ^ (EN) Terence Tao e Tamar Ziegler, The primes contain arbitrarily long polynomial progressions, su arXiv.org. URL consultato il 23 febbraio 2009.
- ^ (EN) Jens Kruse Andersen, Primes in Arithmetic Progression Records, su hjem.get2net.dk. URL consultato il 15 agosto 2008.
- ^ H. Dubner, T. Forbes, N. Lygeros, M. Mizony, H. Nelson, P. Zimmermann, "Ten consecutive primes in arithmetic progression", in Mathematics of Computation, vol. 71, 2002, pp. 1323-1328. URL consultato l'11 gennaio 2009.
- ^ (EN) Tomás Oliveira e Silva, Goldbach conjecture verification, su ieeta.pt. URL consultato il 23 febbraio 2009.
- ^ O. Ramaré, "On Schnirelmann's constant," Ann. Sc. Norm. Super. Pisa, 22:4 (1995) 645-706.
- ^ Deshouillers, Effinger, Te Riele e Zinoviev, "A complete Vinogradov 3-primes theorem under the Riemann hypothesis" (PDF), in Electronic Research Announcements of the American Mathematical Society, vol. 3, 1997, pp. 99-104. URL consultato l'11 gennaio 2009.
- ^ (EN) Chris Caldwell, Fibonacci prime, su primes.utm.edu..
- ^ Chris Caldwell e Yuanyou Cheng, Determining Mills' Constant and a Note on Honaker's Problem (PDF), in Journal of Integer Sequences, vol. 8, 2005. URL consultato il 2009.06.23.
- ^ Paulo Ribenboim, The little book of big primes, 1996, p. 116, ISBN 3-540-97042-8.
- ^ (EN) PRIMES is in P little FAQ, su instantlogic.net, 22 settembre 2008. URL consultato il 9 dicembre 2008.
- ^ (EN) Elliptic curves and ECPP test, su primes.utm.edu, The Prime Pages. URL consultato il 9 dicembre 2008., da Lenstra Jr. K., Lenstra, Jr. H. W., Algorithms in number theory., in Handbook of Theoretical Computer Science Vol A: Algorithms and Complexity, Amsterdam and New York, The MIT Press, 1990, pp. 673-715, MR 1 127 178..
- ^ (EN) Manindra Agrawal, Neeraj Kayal, Nitin Saxena, PRIMES is in P (PDF), su cse.iitk.ac.in. URL consultato il 23 febbraio 2009.
- ^ (EN) Eric W. Weisstein, Number Field Sieve, su mathworld.wolfram.com. URL consultato il 23 febbraio 2009.
- ^ (EN) Burt Kaliski, Announcement of "RSA Factoring Challenge", su groups.google.com, 18 marzo 1991. URL consultato il 23 febbraio 2009.
- ^ (EN) RSA Challenge - FAQ.
- ^ (EN) Eric W. Weisstein, RSA Number, su mathworld.wolfram.com. URL consultato il 23 febbraio 2009.
- ^ Du Sautoy, op. cit., p. 78.
- ^ (EN) Chris Caldwell, The Largest Known Prime by Year: A Brief History, su primes.utm.edu. URL consultato il 23 febbraio 2009.
- ^ Du Sautoy, op. cit., capitolo 9.
- ^ (EN) Titanic Primes Raced to Win $100,000 Research Award, su mersenne.org. URL consultato il 23 febbraio 2009.
- ^ (EN) EFF Cooperative Computing Awards, su eff.org. URL consultato il 23 febbraio 2009.
- ^ (EN) Scoperto un primo di oltre 13 milioni di cifre, su tgdaily.com. URL consultato il 23 febbraio 2009.
- ^ definizione corrispondente a quella data sopra.
- ^ Ad esempio 5 divide e divide 15, mentre 4, che non è primo, divide , ma non divide né 14 né 6.
- ^ Nei domini di Dedekind ogni ideale proprio non nullo si può scrivere come prodotto di ideali primi e tale scrittura è unica a meno del riordino dei fattori.
- ^ Su Mathworld.
- ^ Alcune stelle marine hanno un numero differente di braccia: ad esempio, l'Echinaster luzonicus ha normalmente sei braccia, mentre la Luidia senegalensis ha nove braccia e la Solaster endeca può avere anche 20 braccia.
- ^ (EN) Goles, E., Schulz, O. e M. Markus (2001). "Prime number selection of cycles in a predator-prey model", Complexity 6(4): 33-38.
- ^ (EN) Paulo R. A. Campos, Viviane M. de Oliveira, Ronaldo Giro e Douglas S. Galvão., Emergence of Prime Numbers as the Result of Evolutionary Strategy, in Phys. Rev. Lett., vol. 93, 2004, DOI:10.1103/PhysRevLett.93.098107. URL consultato il 23 febbraio 2009.
- ^ (EN) Invasion of the Brood, in The Economist, 6 maggio 2004. URL consultato il 23 febbraio 2009.
- ^ a b Marcus Du Sautoy, Un divertissement in prima serata, in Matematica e cultura 2006, a cura di Michael Emmer, Springer, 2006, pp. 201-207, ISBN 9788847004641. URL consultato il 27 aprile 2008.
- ^ Peter Hill, The Messiaen companion, Amadeus Press, 1994, ISBN 0-931340-95-0..
Bibliografia
- (EN) Tom M. Apostol, Introduction to Analytic Number Theory, 2ª ed., New York, Apringer-Verlag, 1976, ISBN 0-387-90163-9.
- Carl B. Boyer, Mondadori, 1990, Storia della matematica, ISBN 978-88-04-33431-6. Testo " Milano " ignorato (aiuto);
- John H. Conway, Richard K. Guy, Il libro dei numeri, Milano, Hoepli, 1999, ISBN 88-203-2519-5.
- Harold Davenport, Aritmetica superiore, Bologna, Zanichelli, 1994, ISBN 88-08-09154-6.
- Keith Devlin, Dove va la matematica, Bollati Boringhieri, 1994, ISBN 88-339-1182-9. Testo " Torino " ignorato (aiuto)
- Marcus du Sautoy, L'enigma dei numeri primi, Milano, Rizzoli, 2004, ISBN 88-17-00843-5.
- (EN) Albert Edward Ingham, The Distribution of Prime Numbers, New York, Cambridge Mathematical Library, 1932, ISBN 0-521-39789-8.
- (EN) Leo Moser, An Introduction to the Theory of Numbers (PDF), West Lafayette (Indiana, USA), The Trillia Group, 2004, ISBN 978-1-931705-01-1. URL consultato il 29 gennaio 2009.
- Giulia Maria Piacentini Cattaneo, Algebra - un approccio algoritmico, Padova, Decibel-Zanichelli, 1996, ISBN 978-88-08-16270-0.
Voci correlate
- Principali teoremi e congetture sui numeri primi
- Congettura dei numeri primi gemelli
- Congettura di Goldbach
- Congettura di Opperman
- Ipotesi di Riemann
- Legge di reciprocità quadratica
- Numero primo di Mersenne
- Piccolo teorema di Fermat
- Postulato di Bertrand
- Teorema di Fermat sui primi rappresentabili come somma di due quadrati
- Teorema dei numeri primi
- Teorema dell'infinità dei numeri primi
- Teorema di Mills
- Teorema di Wilson
- Test di Fermat
- Test di Lucas - Lehmer
- Test di Miller - Rabin
Altri progetti
- Wikiquote contiene citazioni sui numeri primi
- Wikimedia Commons contiene immagini o altri file su numeri primi
- Wikinotizie contiene l'articolo Scoperti i due nuovi numeri primi più grandi a distanza di pochi giorni, 18 settembre 2008
- Wikinotizie contiene l'articolo Intervista a Marcus du Sautoy, 4 ottobre 2007
Collegamenti esterni
- (EN) Eric W. Weisstein, Articolo sui numeri primi, in MathWorld, Wolfram Research.
- (IT) Cosa sono i numeri primi (spiega perché 1 non viene considerato primo)
- (IT) Il mistero dei numeri primi e la sicurezza informatica
- (EN) Test interattivo di primalità e fattorizzazione di grandi numeri col metodo delle curve ellittiche
- (EN) The Prime Pages
- (EN) Istituto Clay di matematica - premio per l'ipotesi di Riemann
- (EN) Generatore di numeri primi random di grandi dimensioni (programma in C basato sul OpenSSL)
- (EN) Generatore di numeri primi online.