top

HOME

STORIA

PROPRIETA'

COMPUTAZIONI

PARTICOLARITA'

PROBLEMI APERTI

CURIOSITA'

APPLET

JAVA

VIDEO

SITOGRAFIA

NUMERI PRIMI

 

   

PROPRIETA'

 

Definizione

In matematica, un numero 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 ...

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, dopo oltre un secolo dalla loro formulazione, continuano ad oggi (marzo 2009) ad essere indimostrate.

 

Distribuzione dei numeri primi (linee blu) fino a 400.

 

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.

 

Prime proprietà

 

 

Applicazione del crivello di Eratostene per trovare i numeri primi minori o uguali a 120.

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. 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); 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,

 

c>\sqrt{X}\sqrt{X}=X.

 

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 i 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:  23244 = 22 x 3 x 13 x 149

e ogni altra sua fattorizzazione in numeri primi è ottenuta da questa permutando i fattori. Ad esempio, l'"ulteriore" fattorizzazione:  23244 = 13 x 3 x 2 x 149 x 2

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".

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à, 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:

 

« I numeri primi sono più di una qualsiasi assegnata moltitudine di numeri primi. »

 

La dimostrazione procede per assurdo. Supponendo infatti che esistano solo un numero finito di numeri primi p1,p2,....,pn, si può considerare il numero q = p1p2....pn + 1: questo numero è ovviamente maggiore di 1 e diverso da tutti i numeri primi pi. q può essere primo o composto: se fosse primo avremmo però una contraddizione, perché abbiamo assunto che i pi 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  p1p2....pn   (essendo  uno  dei  numeri  primi),  e  quindi  deve  dividere  la  loro  differenza

q - p1p2....pn = 1 , 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 p1....pn + 1, 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 è 2 x 3 x 5 x 7 x 11 x13 + 1 =30031 = 59 x 509.

Non è noto se in questa successione esistano infiniti numeri primi, anche se è stato congetturato che sia così.

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 formulò una usando metodi di topologia.

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, ed in particolare, usando la notazione O-grande:

 

\sum_{p\leq n} \frac{1}{p}=\ln \ln n+O(1)

 

Questo teorema è dovuto a Eulero, che lo dimostrò nel diciottesimo secolo.

 

Distribuzione dei numeri primi

 

 

Comparazione tra le funzioni π(x) (blu), x / ln x (verde) e Li(x) (rosso), si può notare che l'approssimazione di π(x) con Li(x) è molto migliore di quella con x / ln x

Una volta dimostrato che i numeri primi sono infiniti, ci si può naturalmente chiedere 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 π(x) (detta funzione enumerativa dei primi) e congetturarono che essa fosse approssimativamente

 

\pi(x)\sim\frac{x}{\ln x}

 

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:

 

A\leq \frac{\pi(x)}{\frac{x}{\ln x}} \leq B

 

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:

 

\pi(x)\sim\frac{}{}\mathrm{Li}(x)=\int_2^x \frac{1}{\ln x}\mathrm{d}x

 

Nel 1899 de la Vallée-Poussin dimostrò che l'errore che si commette approssimando π(x) in questo modo è

 

 \pi(x)-\mathrm{Li}(x) = O \left(x \mathrm{e}^{-a\sqrt{\ln x}}\right)=O\left(\frac{x}{(\log x)^m}\right)

 

per una costante positiva a e ogni intero m; tale risultato è stato leggermente migliorato nel corso degli anni. Inoltre, nel 1901 Von Koch mostrò che se l'ipotesi di Riemann è vera, allora si ha la stima molto più precisa:

 

 \pi(x) - \mathrm{Li}(x) = O\left(\sqrt x \ln x\right).

 

Una forma equivalente al teorema dei numeri primi è che p_n, l'n-esimo numero primo, è ben approssimato da nlnn. In effetti, p_n è strettamente maggiore di questo valore.

 

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 (N +1)! + 2, (N + 1)! + 3,...., (N+1)! + N + 1

sono tutti composti: infatti, se i è minore di N, allora (N+1)!+i è divisibile per i, 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:

6! + 2 = 722 = 2 x 361

6! + 3 = 723 = 3 x 241

6! + 4 = 724 = 4 x 181

6! + 5 = 725 = 5 x 145

6! + 6 = 726 = 6 x 121

mentre il valore successivo, 6!+7=727, è primo.

È noto anche che, per ogni n, esiste sempre un primo tra n e 2n (il teorema è detto "postulato di Bertrand", ma a dispetto del nome fu dimostrato nel 1850 da Chebyshev); Paul Erdos rafforzò questo teorema, provando che per ogni numero ε maggiore di 0 esiste un N abbastanza grande tale che, per ogni n>N, esiste un primo tra n e (1+ε)n.

 

Polinomi e progressioni aritmetiche

È stato dimostrato da Legendre alla fine del Settecento 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.

Alcuni polinomi sembrano assumere valori primi "più spesso" degli altri: ad esempio Eulero notò che il polinomio di secondo grado n2 + n + 41 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, non è stato ancora dimostrato che ne esistano infiniti. Più in generale, non c'è alcun polinomio di grado maggiore di uno in una sola variabile 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 ax2 + bxy + cy2 (a patto che a, b e c siano coprimi e che la forma non sia il quadrato di un polinomio di primo grado), mentre nel 1998 John Friedlander e Henryk Iwaniec lo provarono per il polinomio x2 + y4.

 

 

Frazione dei numeri primi congrui a 3 modulo 4.

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, rappresenta la nascita della teoria analitica dei numeri; nel 1949 Atle Selberg ne trovò una elementare, in connessione con la sua dimostrazione del teorema dei numeri primi.

È 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 1 / φ(n) per M che tende all'infinito, ovvero i primi tendono a dividersi equamente tra le φ(n) progressioni di ragione n che contengono più di un primo.

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 numeri primi (teorema di Green-Tao), cioè che per ogni k esiste una progressione aritmetica in cui più di k termini consecutivi sono numeri primi; tale risultato è stato migliorato nel 2006, per includere anche progressioni polinomiali, ovvero espressioni del tipo a+P(n), dove P(x) è un polinomio.

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. È 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.

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.

 

Disuguaglianze coinvolgenti numeri primi

Esistono un certo numero di disuguaglianze che coinvolgono i numeri primi. Ad esempio, come conseguenza della dimostrazione di Euclide dell'infinità dei numeri primi, si ha che: pn+1 < p1p2....pn.

Un'altra disuguaglianza si può ottenere come conseguenza del postulato di Bertrand: poiché infatti esiste un numero primo tra k e 2k per ogni k, allora ponendo k = pn si ha che esiste un numero primo tra pn e 2pn, o, equivalentemente, pn+1 < 2pn.

Da questo, e dal fatto che p1=2, si deduce che:

pn < 2n per ogni n.

Un ulteriore miglioramento della disuguaglianza di Euclide fu provato da H. Bonse nel 1907: il suo risultato (disuguaglianza di Bonse) fu che p2n+1 < p1p2....pn, per n>3. Su questa strada, è stato dimostrato che la disuguaglianza pkn+1 < p1p2....pn, vale definitivamente (ovvero da un certo punto in poi) per ogni k; in particolare, nel 2000 è stato dimostrato che questo vale per ogni n>2k.

 

Confronto tra l'n-esimo numero primo (in blu) e n × lnn (in rosso).

 

Una disuguaglianza simile a quest'ultima, ma di verso opposto, è stata fornita da J. Barkley Rosser nel 1938:  pn > nlnn, per ogni n>1, dove ln indica il logaritmo naturale. Anche tale disuguaglianza è stata migliorata, fino ad arrivare nel 1995 a

pn > n(lnn + lnlnn − 1).

Un'altra disuguaglianza, usata nella "dimostrazione del postulato di Bertrand", si riferisce al prodotto di tutti i primi minori di un certo x:

\prod_{p\leq x} p<4^x

dove i p sono soltanto i numeri primi. Anche questa disuguaglianza è migliorabile: infatti, si può porre 2,83 al posto di 4.

 

TOP