In matematica, un numero primo (in breve anche primo) è un numero intero positivo che abbia esattamente due divisori distinti. In modo equivalente si può definire come un numero naturale maggiore di 1 che sia divisibile solamente per 1 e per sé stesso; al contrario, un numero maggiore di 1 che abbia 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, in quanto tutti gli altri numeri pari sono divisibili per 2.
La successione dei numeri primi comincia con 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139...
Quello di numero primo è uno dei concetti basilari della teoria dei numeri, la parte della matematica che studia i numeri interi: l'importanza sta nella possibilità di costruire con essi, attraverso la moltiplicazione, tutti gli altri numeri interi, nonché l'unicità di tale fattorizzazione. I primi sono inoltre infiniti e la loro distribuzione è tuttora oggetto di molte ricerche.
I numeri primi sono oggetto di studio fin dall'antichità: i primi risultati risalgono agli antichi Greci, e in particolare agli Elementi di Euclide, scritti attorno al 300 a.C. Ciononostante, numerose congetture che li riguardano non sono state ancora dimostrate; tra le più note vi sono l'ipotesi di Riemann, la congettura di Goldbach e quella dei primi gemelli, indimostrate a più di un secolo dalla loro formulazione.
Essi sono rilevanti 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, e in particolare nella crittografia.
Storia Non è noto quando sia stato definito il concetto di numero primo, tuttavia un segnale che fa supporre una qualche consapevolezza della diversità di tali numeri è testimoniato dall'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 e aspettare il secondo millennio a.C.; a tale periodo appartengono infatti alcune tavolette contenenti le soluzioni di alcuni problemi aritmetici che, per essere svolti, richiedono una buona conoscenza della fattorizzazione in primi. Allo stesso millennio appartiene anche il papiro di Rhind (trascritto intorno al 1650 a.C.), che contiene alcune espansioni in frazioni egizie dei numeri nella forma 2⁄n. Le espansioni dei numeri che hanno in comune il più piccolo dei loro fattori sono simili, suggerendo che gli Egizi fossero almeno consapevoli della differenza tra i numeri primi e i composti.
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 primiLibro IX, Proposizione 20. e il lemma di Euclide,Libro VII, Proposizione 30. che prova un'importante caratterizzazione dei numeri primi.Questa proprietà è usata per generalizzare la definizione di numero primo agli anelli. Euclide dimostra anche la possibilità di fattorizzare ogni intero positivo come prodotto di primi.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. () All'antica Grecia dobbiamo anche il crivello di Eratostene, un semplice algoritmo per determinare quali sono i numeri primi.
I secoli seguenti registrarono un certo disinteresse per lo studio dei numeri primi e per diverso tempo non furono dimostrati risultati di particolare rilevanza su questo argomento. L'interesse verso di essi riprese vigore nel diciassettesimo secolo, con le dimostrazioni di nuovi e importanti risultati, alcuni dei quali 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 a n = 4, ma Eulero mostrò che per n = 5 si otteneva un numero composto. A 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 di essi vi sono la divergenza della serie infinita 1⁄2 + 1⁄3 + 1⁄5 + 1⁄7 + 1⁄11 + ..., in cui gli addendi sono gli inversi dei numeri primi, e il cosiddetto prodotto di Eulero, una formula che evidenzia il legame dei primi con la serie armonica.. 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..
Dall'inizio dell'Ottocento, 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 a 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.. Nel 1859 Bernhard Riemann collegò questo problema con il posizionamento degli zeri della funzione zeta di Riemann, una funzione di variabile complessa; 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 numero primo più piccolo è 2 ed è anche l'unico pari; tutti gli altri sono dispari, in quanto ogni numero pari è divisibile anche per 2, non solo per 1 e per se stesso. Nel passato anche 1 fu talvolta considerato numero primo: ad esempio Derrick Norman Lehmer lo incluse nella sua tavola dei numeri primi pubblicata nel 1914.. Oggi tuttavia si tende a escluderlo, in quanto il suo inserimento tra i primi costringerebbe a riformulare in maniera più complessa diversi teoremi, come ad esempio il teorema fondamentale dell'aritmetica, per tenere conto di questo caso speciale.
Un metodo per verificare se un numero n è primo si definisce test di primalità. Un metodo che discende direttamente dalla definizione è controllare che non sia diviso da nessun numero minore di n o, in modo più efficiente, da nessun primo minore 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).
Un antico algoritmo che evita le divisioni è il crivello (ossia setaccio) di Eratostene che, più precisamente, determina l'insieme dei primi minori o uguali a X. Per far ciò, l'algoritmo parte dall'insieme dei numeri naturali compresi tra 2 e X, ed elimina i multipli dei numeri primi individuati in precedenza (perché non sono multipli di numeri più piccoli).Si noti che se si considera che 1 sia primo anche il crivello di Eratostene andrebbe leggermente modificato: se si cominciasse con l'eliminare tutti i multipli di 1 si sarebbe costretti ad eliminare qualsiasi altro numero. In effetti, è possibile migliorare questo algoritmo fermandosi a 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,
La figura a destra mostra il funzionamento dell'algoritmo per X = 120. Analogamente, se si utilizza il metodo delle divisioni per dimostrare la primalità di un numero X si può evitare di controllare la divisibilità di X per numeri maggiori della radice quadrata di X.
In una semplice interpretazione geometrica del concetto di numero primo, 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. Ogni rappresentazione di un numero composto tuttavia ne ammette una simmetrica a seconda che il lato lungo sia orizzontale o verticale; arrestare il crivello (o le divisioni) una volta raggiunta la radice di X significa considerare solo un rettangolo per ciascuna coppia di rettangoli simmetrici.
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 intero positivo diverso da 1 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".Ad esempio in
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 oppure sia a che b. Questa è considerata la definizione stessa 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à 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 esista solo un numero finito di numeri primi p1, p2, ..., pn, si può considerare il numero q = p1p2 ··· pn + 1: questo numero è maggiore di 1 e diverso da tutti i numeri primi pi. Ora, vi sono due possibilità per 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 un fattore primo d, che deve essere uno dei numeri primi pi. Ma allora d divide sia q sia 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.