Numero primo

Da Wikipedia, l'enciclopedia libera.

La distribuzione dei numeri primi (linee blu) fino a 400

In matematica, un numero primo, in breve anche primo, è un numero naturale maggiore di uno, che sia divisibile solamente per sé stesso e per uno. Detto in altro modo, deve avere esattamente due divisori interi positivi distinti: 1 e sé stesso. Il concetto opposto, ossia un numero maggiore di 1 che ha più di due divisori, è detto composto.

Già gli antichi Greci sapevano che i numeri primi sono infiniti, come dimostrato da Euclide verso il 300 a.C. La successione dei numeri primi inizia con 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 ... (Sequenza OEIS:A000040 dell'OEIS).^[1]

I numeri primi sono uno dei concetti basilari della teoria dei numeri, e sono stati studiati sin dall'antichità. Nonostante questo, esistono ancora numerose congetture al riguardo, tra cui le più note sono l'ipotesi di Riemann^[2] e la congettura di Goldbach, che nel 2008 sono ancora non dimostrate, dopo oltre un secolo dalla loro formulazione.

Trovano spazio anche in altri ambiti della matematica, come ad esempio l'algebra. Recentemente sono diventati di importanza cruciale per la crittografia.

[modifica] Esempi

Il concetto di numero primo ammette 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.

[modifica] Storia

Applicazione del crivello di Eratostene per trovare i numeri primi

Non ci sono pervenute notizie certe sullo studio dei numeri primi anteriori all'antica Grecia. Tuttavia, nel papiro di Rhind, trascritto intorno al 1650 a.C., le espansioni in frazioni egiziane dei numeri nella forma ²/_n hanno una forma differente a seconda che n sia primo o composto. Questo può far pensare che gli Egizi avessero qualche conoscenza sui numeri primi che non è giunta fino a noi.

I più antichi studi sui numeri primi che possediamo sono gli Elementi di Euclide, che contengono alcuni risultati fondamentali, tra cui il teorema dell'infinità dei primi^[3] e il lemma di Euclide^[4], mentre il teorema fondamentale dell'aritmetica non è citato esplicitamente. Euclide fornisce inoltre il metodo per generare numeri perfetti a partire dai primi di Mersenne^[5]. All'antica Grecia dobbiamo anche il crivello di Eratostene, un semplice algoritmo per la ricerca dei numeri primi.

Lo studio dei primi riprese nel diciassettesimo secolo, con il lavoro di Pierre de Fermat, che tra l'altro enunciò senza dimostrazione il piccolo teorema di Fermat, e congetturò che tutti i numeri nella forma $2^{2^n} + 1$ (oggi chiamati 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. 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 2^p - 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 ¹/₂ + ¹/₃ + ¹/₅ + ¹/₇ + ¹/₁₁ + ... (dimostrazione), in cui ogni addendo è l'inverso di un numero primo, e il legame dei primi con la serie armonica^[6]. Nel 1747 dimostrò che tutti i numeri perfetti pari derivano dai primi di Mersenne, migliorando il risultato di Euclide.^[7] Nella corrispondenza di Eulero con Christian Goldbach quest'ultimo formulò inoltre la famosa congettura di Goldbach e la sua forma debole, ancora oggi non dimostrate, che riguardano la rappresentazione dei numeri naturali come somma di numeri primi.

Tra la fine del Settecento e l'inizio dell'Ottocento Legendre e Gauss congetturarono indipendentemente che il numero dei primi minori di x tende, al crescere di x, a x/ln(x), dove ln(x) indica il logaritmo naturale di x^[8]. Nel 1859 Bernhard Riemann collegò questa congettura con il posizionamento degli zeri della funzione zeta; questo approccio portò alla dimostrazione, 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. Gauss fu inoltre il primo a dimostrare esplicitamente, nelle Disquisitiones Arithmeticae, il teorema fondamentale dell'aritmetica.

I numeri primi restarono confinati nell'ambito della matematica pura fino agli anni Settanta, quando fu sviluppato il concetto di crittografia a chiave pubblica: il primo algoritmo di questo tipo, l'RSA, ha questo tipo di numeri alla sua base.

A partire dal 1951, tutti i più grandi numeri primi sono stati trovati tramite computer; tale ricerca è stata compiuta anche attraverso progetti di calcolo distribuito, il più famoso dei quali è sicuramente il GIMPS (Great Internet Mersenne Prime Search)^[9].

[modifica] Primalità di 0 e di 1

Il numero 1 non è un primo poiché ha un solo divisore. Il numero 0 non è primo perché ne ha infiniti. L'unico numero primo pari è 2.

La scelta di non includere 1 tra i numeri primi è dovuta a vari motivi: tra questi, c'è il fatto che una tale inclusione costringerebbe a riformulare in modo più complicato diversi teoremi di matematica, come ad esempio il teorema fondamentale dell'aritmetica e il crivello di Eratostene. Ancora nell'Ottocento alcuni matematici includevano tuttavia 1 tra i numeri primi: ad esempio Derrick Norman Lehmer lo incluse nella sua tavola dei numeri primi pubblicata nel 1914.^[10]

[modifica] Scomposizione in fattori primi

Per approfondire, vedi la voce Teorema fondamentale dell'aritmetica.

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 = 2^2 \times 3 \times 13 \times 149$

e ogni altra fattorizzazione di 23244 in numeri primi è ottenuta da questa permutando i fattori.

A causa di questa proprietà ci si riferisce a volte ai numeri primi come agli "atomi dell'aritmetica".^[11]

Questa è tra l'altro la ragione per cui convenzionalmente si esclude 1 dall'insieme dei numeri primi: l'unicità della scomposizione in fattori viene considerata sufficientemente importante da prevalere sulla definizione "ingenua".

La proprietà di fattorizzazione è particolarmente utile anche nel calcolo di particolari funzioni aritmetiche, quelle moltiplicative (ovvero quelle f in cui, per ogni coppia (a,b) di numeri senza fattori comuni si ha f(ab)=f(a)f(b). Infatti attraverso questa proprietà si può "scomporre" il calcolo di f(n), per ogni n, in quello del calcolo dei suoi fattori: se la scomposizione di n è

$n=p_1^{q_1}\cdots p_a^{q_a}$

allora $f(n)=f(p_1^{q_1})\cdots f(p_a^{q_a})$

e generalmente i singoli fattori del prodotto a destra sono più semplici da calcolare. Esempi di funzioni di questo tipo sono la funzione phi di Eulero, la funzione sigma e la funzione divisore.

[modifica] Proprietà

[modifica] Lemma di Euclide

Un'importante proprietà dei primi è espressa dal lemma di Euclide: se un primo p divide il prodotto ab, allora divide a o b. Questa è considerata la definizione di elemento primo in un dominio d'integrità (vedi il paragrafo sulle generalizzazioni), ed è ovvia a partire dal teorema fondamentale dell'aritmetica: la fattorizzazione di ab dovrà 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.

Questa proprietà viene però generalmente usata nella dimostrazione stessa del teorema di fattorizzazione, e per questo non può essere provata usando questo stesso teorema. Il lemma viene quindi generalmente dimostrato partendo dall'identità di Bézout.

[modifica] Valori delle funzioni aritmetiche

Questi sono i valori che assumono alcune funzioni aritmetiche in corrispondenza dei valori primi p:

$\varphi(p)$ =p -1
d(p)=2
$σ(p)$ =p+1
$μ(p)$ =1

Inoltre $\varphi(n)+\sigma(n)=n\cdot d(n)$ se e solo se n è primo.

[modifica] Il piccolo teorema di Fermat

Un'altra proprietà dei primi è espressa dal piccolo teorema di Fermat: secondo questo, per ogni primo p e ogni numero naturale a si ha

$a^p\equiv a\mod p$

oppure, in un'altra forma, per ogni primo p e ogni intero a coprimo con p si ha

$a^{p-1}\equiv 1\mod p$

Questa proprietà può essere usata per verificare se un numero non è primo; tuttavia non può essere usato per controllare se un numero lo è, perché esistono alcuni numeri, detti numeri di Carmichael (il più piccolo dei quali è 561), che pur non essendo primi verificano questa proprietà per ogni a. Recentemente, nel 1994, William Robert Alford, Andrew Granville e Carl Pomerance hanno dimostrato che vi sono infiniti numeri di Carmichael.^[12]

[modifica] Polinomi

Dato un numero n, il polinomio

$P(x)=x^{n-1}+x^{n-2}+\cdots+x^2+x+1$

è irriducibile su $\mathbb{Q}$ se e solo se n è primo. Se infatti non è primo (ad esempio si ha n=ab) 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, e scomporre P(x) come

$x^9+x^8+\ldots+x^2+x+1=x^8(x+1)+x^6(x+1)+x^4(x+1)+x^2(x+1)+(x+1)=(x^8+x^6+x^4+x^2+1)(x+1)$

ottenendo quindi una scomposizione. Per dimostrare l'inverso si può usare l'invece il criterio di Eisenstein.

[modifica] Fattoriali

Il teorema di Wilson afferma che

$(p-1)!\equiv -1\mod p$

se e solo se p è primo. Con tale teorema si può quindi costruire un test di primalità, che però risulta essere molto costoso da calcolare a causa della presenza del fattoriale.

[modifica] Infinità

Per approfondire, vedi la voce Teorema dell'infinità dei numeri primi.

I numeri primi sono infiniti. La più antica dimostrazione pervenutaci è quella di Euclide. La proposizione 20 del Libro IX degli Elementi afferma infatti che I numeri primi sono più di una qualsiasi assegnata moltitudine di numeri primi. La sua dimostrazione parte da un qualunque insieme di numeri primi $p 1, p 2,..., p n$ , e costruisce un numero primo diverso da tutti i $p i$ . Si inizia moltiplicando tra di loro tutti questi numeri e sommando un'unità, ottenendo come risultato un nuovo numero q che potrà essere o non essere primo. Se q è primo, la dimostrazione è terminata; altrimenti esso dovrà avere almeno un divisore d primo. Per costruzione, però, d non può essere nessuno dei $p i$ ; infatti la divisione $q / p i$ dà sempre 1 come resto, quindi, per ogni $i$ , $p i$ non divide $q$ , e quindi $p i$ non divide neanche il suo divisore d. Pertanto, d è l'ulteriore numero primo cercato.

Ecco alcuni esempi numerici. Partendo da 2 e 3, otteniamo $(2\times 3)+1 = 7$ che è un numero primo; aggiungendolo agli altri arriviamo a $(2\times 3 \times 7)+1 = 43$ che è ancora primo; invece $(2\times 3\times7 \times 43)+1 = 1807$ che non è primo ma ha il fattore primo 13.

Altre dimostrazioni sono state create nel corso dei secoli: Eulero dimostrò questo teorema dalla divergenza della serie armonica, Goldbach attraverso i numeri di Fermat, mentre Harry Furstenberg ne trovò una attraverso la topologia.^[13]

[modifica] 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

Oltre all'infinità dei primi, un altro soggetto di studio è stata la loro distribuzione. Tale studio fu iniziato verso la fine del XVIII secolo indipendentemente da Gauss e da Legendre, che congetturarono che il numero di primi minori o uguali di un dato numero x (indicato con $π(x)$ ) fosse approssimativamente

$\pi(x)\sim\frac{x}{\ln x}$ ^[14]

Tale congettura è stata dimostrata nel 1896 da Jacques Hadamard e da Charles Jean de la Vallée-Poussin in lavori simultanei ma indipendenti usando metodi che coinvolgevano la funzione zeta di Riemann; tale enunciato è oggi noto con il nome di teorema dei numeri primi. Nel 1949 Atle Selberg dimostrò il teorema usando metodi elementari, ovvero senza l'uso dei metodi dell'analisi.

In seguito Gauss introdusse una stima più precisa, secondo la quale

$\pi(x)\sim\frac{}{}\mathrm{Li}(x)$

dove Li(x) è la funzione logaritmo integrale. Nel 1899 de la Vallée-Poussin riuscì a dimostrare che l'errore che si commette approssimando $π(x)$ con $Li(x)$ è

$\pi(x)-{\rm Li} (x) = O \left(x \mathrm{e}^{-a\sqrt{\ln x}}\right)$

(nella notazione O-grande) per una costante positiva a e tale risultato è stato leggermente migliorato nel corso degli anni. Inoltre, nel 1901 Koch mostrò che se l'ipotesi di Riemann è vera allora si ha la stima più precisa

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

È noto anche che esiste sempre un primo tra n e 2n, per ogni n (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 k maggiore di 1 esiste un N abbastanza grande tale che per ogni n>N esiste un primo tra n e kn.^[15]

[modifica] Formule per i numeri primi

Per approfondire, vedi la voce Formula per i numeri primi.

Non è stata ancora trovata una formula chiusa per i numeri primi, ovvero una formula che generi, dato n, l'n-esimo numero primo, né una formula che generi soltanto numeri primi. È stato tuttavia dimostrato (teorema di Mills) che esiste una costante $θ$ tale che

$\lfloor \theta^{3^n}\rfloor$

è sempre un numero primo. Tuttavia, non si conosce nessuna formula chiusa per il calcolo della 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.

È stato dimostrato 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)\equiv 0\mod p$ . Ma $P(1)\equiv 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); ma questo è assurdo perché nessun polinomio può assumere uno stesso valore per più volte che il proprio grado.

Alcuni polinomi producono però valori primi "più spesso" degli altri: ad esempio Eulero notò che il polinomio d i secondo grado $n 2 + n + 41$ produce numeri primi per ogni valore di n compreso tra 0 e 39; tuttavia, sebbene nei primi 10 milioni di valori che questa funzione assume circa 1/3 siano primi,^[16] non è stato ancora dimostrato che ne esistano infiniti. Più in generale, non c'è alcun polinomio di grado maggiore di uno di cui sia stato dimostrato che assume infiniti valori primi.

A seguito della dimostrazione del teorema di Matiyasevich, sono state trovate varie formule i cui valori positivi sono soltanto primi. Un esempio è il polinomio in 26 variabili (da a a z nell'alfabeto latino)

$(k+2) \left \{ {( wz + h + j - q)^2 - [ (gk + 2g + k + 1)(h + j) + h - z]^2 + }\right.$

- [16(k + 1) 3 (k + 2)(n + 1) 2 + 1 - f 2] 2 - (2 n + p + q + z - e) 2 +

$- [ e^3(e + 2)(a + 1)^2 + 1 - o^2]^2 - [(a^2 - 1)y^2 + 1 - x^2]^2 +\,$

$- [ 16r^2y^4(a^2 - 1) + 1 - u^2]^2 - ( n + l + v - y)^2 - [(a^2 - 1)l^2 + 1 - m^2]^2 +\,$

$- ( ai + k + 1 - l - i)^2- \left\{ { \{[a + u^2(u^2 - a)]^2 - 1\}(n + 4dy)^2 + 1 +}\right. \,$

$\left. {- (x + cu)^2} \right\}^2 - [ p + l(a - n - 1)+ b(2an + 2a - n^2 - 2n - 2) - m]^2 +\,$

$\left. {- [ q + y(a - p - 1) + s(2ap + 2a - p^2 - 2p - 2) - x]^2 - [ z + pl(a - p) +} \right. \,$

$\left. {+ t(2ap - p^2 - 1) - pm]^2} \right \}$

L'utilità di queste formule è però notevolmente diminuita dal fatto che la maggior parte dei valori che assume sono negativi.

[modifica] Numeri primi e progressioni aritmetiche

A differenza di quanto accade per i polinomi di grado più alto, Dirichlet dimostrò nel 1837 che ogni progressione aritmetica contiene infiniti numeri primi. La prima dimostrazione dei 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.

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.

[modifica] Test di primalità

Per approfondire, vedi la voce Test di primalità.

Il più antico e semplice metodo per controllare se un numero N sia primo o no è sicuramente quello di "divisione per tentativi", ovvero provare a dividere N per i numeri primi^[17] minori di $\sqrt{N}$ .^[18] Sebbene molto semplice da descrivere e da implementare come algoritmo, tale metodo è, per numeri grandi, estremamente lungo.

Esistono altri metodi per verificare la primalità di un numero: alcuni di essi, come il test di Miller-Rabin, sono probabilistici, ovvero danno una risposta certa solo se il numero non è primo; altri si applicando solo a classi particolari di numeri: ad esempio il test di Lucas-Lehmer si applica solo agli interi nella forma $2 n - 1$ . Negli ultimi anni sono stati sviluppati algoritmi per testare la primalità di un numero che hanno complessità logaritmica (come, ad esempio, l'algoritmo AKS), dimostrando così che la complessità computazionale del test di primalità sta nella classe di complessità P^[19].

Un tipo diverso di test di primalità è dato dal crivello di Eratostene, che genera tutti i numeri primi compresi tra 1 e N.

[modifica] Algebra

[modifica] Aritmetica modulare

I numeri primi hanno un ruolo centrale anche nell'algebra. Ad esempio, nell'aritmetica modulare, si ha che l'anello $\mathbb{Z}/n\mathbb{Z}$ delle classi di resto è 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.

[modifica] Teoria dei gruppi

Nella teoria dei gruppi, i gruppi con un numero primo di elementi sono ciclici e dunque abeliani. Inoltre, ogni gruppo abeliano finito è isomorfo al prodotto diretto di un numero finito di gruppi ciclici ognuno dei quali ha come cardinalità la potenza di un primo.

Inoltre, i teoremi di Sylow garantiscono che in ogni gruppo di ordine n esiste almeno un sottogruppo per ogni pⁱ, dove p è un numero primo e pⁱ divide n.

[modifica] 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 è isomofo al campo delle classi di resto $\mathbb{Z}/p\mathbb{Z}$ .

Si mostra poi che tutti i campi finiti hanno un numero di elementi che o è primo o è una potenza di un primo. In particolare, ogni campo con un numero primo p di elementi coincide è isomorfo a $\mathbb{Z}/p\mathbb{Z}$ , mentre ogni campo con pⁿ elementi è un'estensione di Galois di un campo con p elementi.

[modifica] Numeri p-adici

Per approfondire, vedi la voce Numero p-adico.

Per ogni primo p si può introdurre una norma sui numeri razionali $\mathbb{Q}$ tale 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 dalla norma p-adica, si ottiene un campo, indicato con $\mathbb{Q}_p$ , 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 $\mathbb{Z}/p\mathbb{Z},~\mathbb{Z}/p^2\mathbb{Z},~ \mathbb{Z}/p^3\mathbb{Z}\ldots$ . Lo studio dei numeri p-adici e delle loro proprietà è uno degli argomenti principali della teoria dei numeri.

[modifica] Generalizzazioni

Rappresentazione dei primi di Gauss di norma minore o uguale a 500. I primi di Gauss sono, per definizione, gli elementi tra gli interi di Gauss che sono primi.

Il concetto di numero primo viene esteso anche in altri campi della matematica.

[modifica] 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, non equivalenti fra loro in generale:

un elemento è irriducibile se è un elemento non invertibile che non può essere scritto come il prodotto di due elementi non invertibili (definizione corrispondente a quella data sopra);
un elemento è primo se ogni volta che divide il prodotto $a b$ , allora divide $a$ oppure $b$ (ad esempio: 5 divide $45 = 15 \times 3$ e divide 15; 4, che non è primo, divide $84 = 14 \times 6$ , ma non divide né 14 né 6).

Nell'anello degli interi le due definizioni sono equivalenti, e più in generale sono equivalenti in un anello 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 $ab\in I$ almeno uno tra a e b appartiene a I. Questa definizione è molto vicina a quella degli ordinari numeri primi, tanto che nell'anello $\mathbb{Z}$ degli interi gli ideali primi sono esattamente (2), (3), (5)..., ovvero quelli generati dai numeri primi. 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^[20]

[modifica] 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. Nella teoria dei nodi vi è 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. 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.

[modifica] Problemi aperti

Molte congetture riguardanti i numeri primi sono ancora aperte.

Tra di esse, la più nota è forse la congettura di Goldbach, che asserisce che ogni numero intero pari maggiore di due è somma di due numeri primi, e quindi che ogni intero dispari è somma di tre primi.^[21]

La congettura dei numeri primi gemelli asserisce che esistono infinite coppie di numeri primi la cui differenza è 2.^[22] Una sua generalizzazione è la congettura di Polignac, secondo la quale per ogni intero n esistono infinite coppie di primi la cui differenza è 2n.

L'ipotesi di Riemann, uno dei problemi insoluti più importanti di tutta la matematica, riguarda la frequenza dei numeri primi, in connessione alla funzione zeta di Riemann. Era uno dei ventitré problemi di Hilbert, enunciati nel 1900, ed è stato scelto fra i sette problemi per il millennio nel 2000.

Altri problemi aperti riguardano l'esistenza o meno di infiniti numeri primi in una certa forma: ad esempio non è ancora noto se sono infiniti i primi che possono essere scritti nella forma n²+1, i primi dei quali sono 2, 5, 17, 37 (Sequenza OEIS:A002496 dell'OEIS), oppure se, dato un qualunque numero naturale n, esiste sempre un primo tra n² e (n+1)² (tale problema è noto come congettura di Legendre).

[modifica] Applicazioni

Praticamente tutti i grandi matematici si sono occupati, prima o poi, di numeri primi; recentemente i numeri primi (assieme alla branca della matematica che li studia, la teoria dei numeri) hanno trovato applicazione nel campo della crittologia: nell'RSA, uno dei pricipali algoritmi di crittografia asimmetrica, la decrittazione del messaggio richiede la fattorizzazione di un numero di grandi dimensioni, problema che ad oggi rientra nella categoria dei problemi con complessità NP.

[modifica] Numeri primi in natura

Una Magicicada con periodo di 17 anni

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. Per esempio, la maggior parte delle stelle marine hanno 5 braccia, e 5 è un numero primo. In ogni modo non è stato trovato alcun motivo evidente per supporre che le stelle marine abbiano 5 braccia perché 5 è primo. Per la verità, 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. 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,^[23] 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 sia di tempo sia un numero primo di anni è la difficoltà per un predatore di evolversi specializzandosi come predatori delle Magicicada:^[24] 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.^[25] Sebbene esile, questo vantaggio evolutivo sembra essere stato sufficiente a selezionare cicale il cui periodo è 13 o 17 anni.

[modifica] Numeri primi nell'arte e nella letteratura

I numeri primi hanno influenzato molti artisti e scrittori. Il compositore francese Olivier Messiaen usò i numeri primi per create musica non metrica: in opere come La Nativité du Seigneur (1935) o Quatre études de rythme (1949-50) impiega simultaneamente motivi la cui lunghezza è n numero primo per creare ritmi imprevedibili. Secondo Messiaen questo modo di comporre era "ispirato dai movimenti dalla natura, movimenti di durate libere e disuguali".^[26]

Nel romanzo di fantascienza Contact, di Carl Sagan, è suggerito che i numeri primi possano essere usati dagli alieni per comunicare.

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 o A beautiful mind.

[modifica] Principali teoremi e congetture sui numeri primi

Congettura di Goldbach
Congettura di Opperman
Congettura dei numeri primi gemelli
Teorema di Shimura-Taniyama (dimostrato parzialmente da Andrew Wiles e integralmente da Brian Conrad, Fred Diamond, Richard Taylor e Christoph Breuil nel 2005)
Ipotesi di Riemann
Legge di reciprocità quadratica (Teorema dei numeri primi di Gauss)
Numero primo di Mersenne
Piccolo teorema di Fermat
Teorema di Fermat sui primi rappresentabili come somma di due quadrati
Teorema dei numeri primi
Teorema dell'infinità dei numeri primi
Postulato di Bertrand (dimostrato nel 1850 da Cebicev)
Teorema di Mills
Teorema di Wilson
Test di Lucas - Lehmer
Test di Fermat
Test di Miller - Rabin

[modifica] Note

^ 4 è divisibile per 2, 6 è divisibile per 3, 8 è divisibile per 2, 9 è divisibile per 3, 10 è divisibile per 2, e così via.
^ Per l'ipotesi di Riemann è stata presentata una dimostrazione da Louis de Branges de Bourcia, la cui correttezza è ancora al vaglio.
^ Libro IX, Proposizione 20
^ Libro VII, Proposizione 30
^ Libro IX, Proposizione 36
^ Marcus Du Sautoy. L'enigma dei numeri primi. Milano, Rizzoli, 2004. ISBN 8817008435, p.149
^ (EN) J.J.O'Connor, E. F. Robertson. Perfect numbers - History and Theory. MacTutor, dicembre 2001. URL consultato il 03.04.2008.
^ Du Sautoy, op. cit., capitolo 2
^ (EN) Sito ufficiale del GIMPS
^ Conway e Guy, in Il libro dei numeri, p.111
^ Ad esempio in du Sautoy, L'enigma dei numeri primi
^ W. R. Alford, A. Granville, e C. Pomerance. "There are Infinitely Many Carmichael Numbers." Annals of Mathematics 139 (1994) 703-722.
^ (EN) Furstenberg, Harry. (1955). On the infinitude of primes. Amer. Math. Monthly 62 (5): 353. DOI:10.2307/2307043.
^ Con questa espressione si intende che il limite del rapporto tra queste due espressioni tende a 1 quando x tende a infinito.
^ Du Sautoy, op. cit., p.312
^ Devlin, in Dove va la matematica, p.73
^ Se N è diviso da un numero a, allora è diviso da tutti i fattori di a. Quindi se a non fosse primo dovremmo aver già trovato un altro fattore p<a.
^ Data una fattorizzazione N=ab, se entrambi a e b fossero strettamente maggiori di $\sqrt{N}$ , si avrebbe $ab>\sqrt{N}\sqrt{N}=N$ , ovvero ab>N, cosa che è in contrasto con l'ipotesi ab=N. Quindi basta considerare i primi minori di $\sqrt{N}$
^ cioè vi è un'algoritmo per determinare se un numero N è primo che ha costo computazionale non oltre un polinomio di grado n del numero delle cifre di N. Da notare che poiché $\forall x>0 \,: x > \operatorname {log}\,x$ , anche una potenza del logaritmo viene considerata polinomiale.
^ Nei domini di Dedekind ogni ideali proprio non nullo si può scrivere come prodotto di ideali primi e tale scrittura è unica a meno del riordino dei fattori.
^ Questa congettura è anche stata studiata indipendentemente, ed è nota come congettura debole di Goldbach
^ A parte 2 e 3, questa è la minima distanza possibile per i primi, perché in una coppia di interi consecutivi uno è pari, cioè divisibile per 2, quindi non primo
^ (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. (2004). Emergence of Prime Numbers as the Result of Evolutionary Strategy. Phys. Rev. Lett. 93. DOI:10.1103/PhysRevLett.93.098107. URL consultato il 2006-11-26.
^ (EN) Invasion of the Brood in The Economist. 6 maggio 2004. URL consultato il 2006-11-26.
^ Peter Hill. The Messiaen companion. Amadeus Press, 1994. ISBN 0-931340-95-0

[modifica] Bibliografia

(IT) Keith Devlin, Dove va la matematica. Bollati Boringhieri, Torino, 1994. ISBN 8833911829
(IT) John H. Conway, Richard K. Guy, Il libro dei numeri. Hoepli, Milano, 1999. ISBN 8820325195
(IT) Marcus du Sautoy, L'enigma dei numeri primi. Rizzoli, Milano, 2004. ISBN 8817008435
(IT) Harold Davenport, Aritmetica superiore. Zanichelli, Bologna, 1994. ISBN 8808091546
(IT) Giulia Maria Piacentini Cattaneo, Algebra - un approccio algoritmico. Decibel-Zanichelli, Padova 1996, ISBN 9788808162700
(EN) Albert Edward Ingham, The Distribution of Prime Numbers. Cambridge Mathematical Library, New York, 1932. ISBN 0521397898
(IT) Carl B. Boyer, Storia della matematica. Mondadori, Milano, 1990. ISBN 9788804334316

[modifica] Voci correlate

[modifica] Altri progetti

Wikimedia Commons contiene file multimediali su numeri primi
Wikiquote contiene citazioni sui numeri primi
Articolo su Wikinotizie: Intervista a Marcus du Sautoy 4 ottobre 2007

[modifica] Collegamenti esterni

Algebra

Numeri: Naturale · Intero · Razionale · Algebrico · Trascendente · Reale · Complesso

Algebra elementare: Numero primo · MCD · mcm · Algoritmo di Euclide · Equazione · Disequazione · Polinomio · Aritmetica modulare
Teoria dei gruppi: Gruppo (finito · ciclico · abeliano) · Omomorfismo · Sottogruppo normale · Teorema di isomorfismo · Permutazione
Teoria degli anelli: Anello · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice
Teoria dei campi: Campo · Estensione di campi · Chiusura algebrica · Teorema fondamentale dell'algebra · Teoria di Galois

Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica

Categorie: Numeri primi | Matematica di base | Voci di qualità su ru.wiki

See also ebooksgratis.com: no banners, no cookies, totally FREE.