Numero primo: differenze tra le versioni

Versione delle 14:37, 1 set 2009

Versione attuale delle 07:29, 2 set 2025

(830 versioni intermedie di oltre 100 utenti non mostrate)

Riga 1:

[[File:Prime num le 400.png|thumb|400pxupright=1.8|La distribuzione dei numeri primi (linee blu) fino a 400]]

In [[matematica]], un '''numero primo''' (in breve anche '''primo''') è un [[numero intero]] positivo che abbia esattamente due [[Divisore|divisori]] distinti. In modo equivalente si può definire come un [[numero naturale]] maggiore di uno1 che sia [[divisibilitàdivisore|divisibile]] solamente per [[uno1 (numero)|1]] e per sé stesso; al contrario, un numero maggiore di 1 che haabbia più di due divisori è detto [[numero composto|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 [[numeri pari e dispari|pari]] è 2, poichéin quanto tutti gli altri numeri pari sono divisibili anche per 2.

La [[successione (matematica)|successione]] dei numeri primi comincia con [[2 (numero)|2]], [[3 (numero)|3]], [[5 (numero)|5]], [[7 (numero)|7]], [[11 (numero)|11]], [[13 (numero)|13]], [[17 (numero)|17]], [[19 (numero)|19]], [[23 (numero)|23]], [[29 (numero)|29]], [[31 (numero)|31]], [[37 (numero)|37]], [[41 (numero)|41]], [[43 (numero)|43]], [[47 (numero)|47]], [[53 (numero)|53]], [[59 (numero)|59]], [[61 (numero)|61]], [[67 (numero)|67]], [[71 (numero)|71]], [[73 (numero)|73]], [[79 (numero)|79]], [[83 (numero)|83]], [[89 (numero)|89]], [[97 (numero)|97]], [[101 (numero)|101]], [[103 (numero)|103]], [[107 (numero)|107]], [[109 (numero)|109]], [[113 (numero)|113]], [[127 (numero)|127]], [[131 (numero)|131]], [[137 (numero)|137]], [[139 (numero)|139]]...<ref>{{Cita web|url=https://oeis.org/A000040|titolo=The on-line encyclopedia of integer sequences|editore=The OEIS Foundation|lingua=en|accesso=28 dicembre 2018|urlarchivio=https://web.archive.org/web/20180129172600/https://oeis.org/A000040|dataarchivio=29 gennaio 2018|urlmorto=no}}</ref>

La [[successione (matematica)|successione]] dei numeri primi inizia con [[due|2]], [[tre|3]], [[cinque|5]], [[sette|7]], [[undici|11]], [[tredici|13]], [[diciassette|17]], [[diciannove|19]], [[ventitré|23]], [[ventinove|29]], [[trentuno|31]], [[trentasette|37]] ... {{OEIS|A000040}}.

IQuello numeridi priminumero sonoprimo è uno dei concetti basilari della [[teoria dei numeri]], la parte della matematica che studia i [[numero intero|numeri interi]]: alla base di questa l'importanza vista è lanella possibilità di costruire con essi, attraverso la moltiplicazione, tutti gli altri numeri interi;, inoltrenonché l'unicità di tale [[fattorizzazione]] è unica. I primi sono inoltre [[infinito (matematica)|infiniti]], e moltela ricercheloro sonodistribuzione stateè compiutetuttora peroggetto comprenderedi lamolte loro distribuzionericerche.

I numeri primi sono statioggetto di studiatistudio sinfin dall'antichità: i primi risultati risalgono infatti agli [[antichi [[Greci]], e in particolare agli ''[[Elementi (Euclide)|Elementi]]'' di [[Euclide]], scritti attorno al [[300 a.C.]]; nonostante questoCiononostante, esistono ancora numerose [[congettura|congetture]] ache riguardoli cheriguardano non sono state ancora [[dimostrazione|dimostrate]].; Tra di esse,tra le più note vi sono l'[[ipotesi di Riemann]], la [[congettura di Goldbach]] e laquella [[Congettura dei numeri primi gemelli|congettura dei primi gemelli]], cheindimostrate ada oggipiù (giugno 2009), dopo oltredi un secolo dalla loro formulazione, non sono ancora state dimostrate.

TrovanoEssi spaziosono inoltrerilevanti anche in molti altri ambiti della matematica pura, come ad esempio l'[[algebra astratta|algebra]] o la [[geometria]]; recentemente hanno assunto un'importanza cruciale anche nella matematica applicata, cone in particolare riferimento allanella [[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 [[II millennio a.C.|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.<ref>{{cita libro|autore=[[Otto Eduard Neugebauer|Otto Neugebauer]]|titolo=Le scienze esatte nell'antichità|editore=Feltrinelli|città=Milano|anno=1974|capitolo=Capitolo 2|ISBN=88-07-22281-7}}</ref> Allo stesso millennio appartiene anche il [[papiro di Rhind]] (trascritto intorno al 1650 a.C.), che contiene alcune espansioni in [[Frazione egizia|frazioni egizie]] dei numeri nella forma ²⁄_''n''. Le espansioni dei numeri che hanno in comune il più piccolo dei loro fattori sono simili, suggerendo che gli [[Antico Egitto|Egizi]] fossero almeno consapevoli della differenza tra i numeri primi e i composti.<ref>{{cita web|url=http://mathpages.com/home/kmath340/kmath340.htm|titolo=Egyptian Unit Fractions|sito=Mathpages|accesso=14 gennaio 2011}}</ref>

[[File:Oxyrhynchus papyrus with Euclid's Elements.jpg|thumb|left|Un frammento degli ''Elementi'' di Euclide rinvenuto a [[Ossirinco]].]]

La prima traccia incontestabile di un vero studio dei numeri primi è costituita dagli ''[[Elementi (Euclide)|Elementi]]'' di [[Euclide]], un libro composto tra il [[IV secolo a.C.|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 numeri primi|teorema dell'infinità dei primi]]<ref>Libro IX, Proposizione 20.</ref> e il [[lemma di Euclide]],<ref>Libro VII, Proposizione 30.</ref> che prova un'importante caratterizzazione dei numeri primi.<ref group="N">Questa proprietà è usata per generalizzare la definizione di numero primo agli [[anello (algebra)|anelli]].</ref> Euclide dimostra anche la possibilità di [[fattorizzazione|fattorizzare]] ogni intero positivo come prodotto di primi.<ref>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 [[Carl Friedrich Gauss|Gauss]] nelle ''[[Disquisitiones Arithmeticae]]''. ({{cita|Boyer|p. 582|Boyer}})</ref> All'antica Grecia dobbiamo anche il [[crivello di Eratostene]], un semplice [[algoritmo]] per determinare quali sono i numeri primi.

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 [[II millennio a.C.|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.<ref>{{cita libro|autore=[[Otto Neugebauer]]|titolo=Le scienze esatte nell'antichità|editore=Feltrinelli|città=Milano|anno=1974|id=ISBN 8807222817|capitolo=Capitolo 2}}</ref> Allo stesso millennio appartiene anche il [[papiro di Rhind]] (trascritto intorno al [[1650 a.C.]]), che contiene alcune espansioni in [[frazione egiziana|frazioni egiziane]] dei numeri nella forma ²/_''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.

[[File:Pierre de Fermat.jpg|thumb|[[Pierre de Fermat]]]]

[[File:Oxyrhynchus papyrus with Euclid's Elements.jpg|230px|thumb|left|Un frammento degli ''Elementi'' di Euclide rinvenuto a [[Ossirinco]]]]

I secoli seguenti registrarono un certo disinteresse per lo studio dei numeri primi<ref>{{cita web|autore=John J. O'Connor|autore2=Edmund F. Robertson|url=https://mathshistory.st-andrews.ac.uk/HistTopics/Prime_numbers/|titolo=Prime numbers|sito=[[MacTutor]]|accesso=14 gennaio 2011|lingua=en}}</ref> e per diverso tempo non furono dimostrati risultati di particolare rilevanza su questo argomento. L'interesse verso di essi riprese vigore nel [[XVII secolo|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 [[Aritmetica modulare|congruenze modulo un primo]], noto come "[[piccolo teorema di Fermat]]", e il [[teorema di Fermat sulle somme di due quadrati|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 2^2ⁿ + 1 (oggi chiamati in suo onore [[numero di Fermat|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 2^''p'' − 1, con ''p'' primo, che oggi sono chiamati in suo onore [[numero primo di Mersenne|primi di Mersenne]].

La prima traccia incontestabile di un vero studio dei numeri primi è costituita dagli ''[[Elementi (Euclide)|Elementi]]'' di [[Euclide]], un libro composto tra il [[IV secolo a.C.|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 numeri primi|teorema dell'infinità dei primi]],<ref>Libro IX, Proposizione 20.</ref> e il [[lemma di Euclide]],<ref>Libro VII, Proposizione 30.</ref> che prova un'importante caratterizzazione dei numeri primi.<ref>Questa proprietà verrà usata per generalizzare la definizione di numero primo agli [[anello (algebra)|anelli]].</ref> Euclide dimostra anche la possibilità di [[fattorizzazione|fattorizzare]] ogni intero positivo come prodotto di primi.<ref>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 [[Carl Friedrich Gauss|Gauss]] nelle ''[[Disquisitiones Arithmeticae]]''.</ref> All'antica Grecia dobbiamo anche il [[crivello di Eratostene]], un semplice [[algoritmo]] per determinare quali sono i numeri primi.<ref>Per quanto semplice, tale algoritmo è troppo costoso dal punto di vista computazionale e quindi non è generalmente usato nelle applicazioni pratiche.</ref>

[[File:Pierre de Fermat.jpg|230px|thumb|Pierre de Fermat]]

Altri risultati vennero ottenuti da Eulero nel corso del [[XVIII secolo|diciottesimo secolo]]: tra di essi vi sono la [[limite di una successione|divergenza]] della [[serie (matematica)|serie]] infinita ¹⁄₂ + ¹⁄₃ + ¹⁄₅ + ¹⁄₇ + ¹⁄₁₁ + ..., in cui gli addendi sono gli inversi dei numeri primi, e il cosiddetto [[formula prodotto di Eulero|prodotto di Eulero]], una formula che evidenzia il legame dei primi con la [[serie armonica]].<ref>{{cita|Du Sautoy|p. 149|Sautoy}}.</ref> 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.<ref>{{cita|Apostol|p. 9|Apostol}}.</ref>

I secoli seguenti registrarono un certo disinteresse per lo studio dei numeri primi<ref>{{cita web|url=http://www-history.mcs.st-andrews.ac.uk/history/HistTopics/Prime_numbers.html|titolo=Prime numbers|accesso=23 febbraio 2009|lingua=en}}</ref> e per diverso tempo non furono provati risultati di particolare rilevanza su questo argomento. L'interesse per i numeri primi riprese vigore nel [[XVII secolo|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 [[Aritmetica modulare|congruenze modulo un primo]], noto come "[[piccolo teorema di Fermat]]", e il [[teorema di Fermat sulle somme di due quadrati|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 2^2ⁿ + 1 (oggi chiamati in suo onore [[numero di Fermat|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 2^''p'' - 1, con ''p'' primo, che oggi sono chiamati in suo onore [[numero di Mersenne|primi di Mersenne]].

Dall'inizio dell'[[XIX secolo|Ottocento]], l'attenzione di molti matematici si rivolse allo studio della distribuzione [[stima asintotica|asintotica]] dei primi, ossia allo studio dell'andamento della funzione che conta i primi minori o uguali a ''x''.<ref>{{cita|Apostol|p. 8|Apostol}}.</ref> [[Adrien-Marie Legendre|Legendre]] e [[Carl Friedrich Gauss|Gauss]] congetturarono indipendentemente che tale funzione [[limite di una funzione|tende]], al crescere di ''x'', a ''x'' / ln(''x''), dove ln(''x'') indica il [[logaritmo naturale]] di ''x''.<ref>{{cita|Du Sautoy|capitolo 2|Sautoy}}.</ref> Nel 1859<ref>{{cita web|url=https://www.claymath.org/millennium/Riemann_Hypothesis/1859_manuscript/|titolo=Riemann's 1859 Manuscript|accesso=14 gennaio 2011|urlmorto=sì|urlarchivio=https://web.archive.org/web/20130523061451/http://www.claymath.org/millennium/Riemann_Hypothesis/1859_manuscript/|dataarchivio=23 maggio 2013}}</ref> [[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 [[Jacques Hadamard|Hadamard]] e [[Charles Jean de la Vallée-Poussin|de la Vallée Poussin]] nel 1896. Tale risultato è oggi noto col nome di [[teorema dei numeri primi]].

Altri risultati vennero ottenuti da Eulero nel corso del [[XVIII secolo|diciottesimo secolo]], tra cui la [[limite di una successione|divergenza]] della [[serie infinita]] ¹/₂ + ¹/₃ + ¹/₅ + ¹/₇ + ¹/₁₁ + ..., in cui gli addendi sono gli inversi dei un numeri primi, e il cosiddetto [[formula prodotto di Eulero|prodotto di Eulero]], una formula che evidenzia il legame dei primi con la [[serie armonica]].<ref>Du Sautoy, ''[[L'enigma dei numeri primi]]'', p. 149.</ref> 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.

I numeri primi restarono confinati nell'ambito della matematica pura fino agli [[Anni 1970|anni settanta]], quando venne sviluppato il concetto di [[Crittografia asimmetrica|crittografia a chiave pubblica]]; il primo algoritmo di questo tipo, l'[[RSA (crittografia)|RSA]], sfrutta infatti la difficoltà di [[fattorizzazione|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]].

Dalla fine del Settecento, l'attenzione di molti matematici si rivolse allo studio della distribuzione [[stima asintotica|asintotica]] dei primi, ossia allo studio dell'andamento della funzione che conta i primi minori o uguali ad ''x''. [[Adrien-Marie Legendre|Legendre]] e [[Carl Friedrich Gauss|Gauss]] congetturarono indipendentemente che tale funzione [[limite di una funzione|tende]], al crescere di ''x'', a ''x'' / ln(''x''), dove ln(''x'') indica il [[logaritmo naturale]] di ''x''.<ref>Du Sautoy, op. cit., capitolo 2.</ref> 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 [[Jacques Hadamard|Hadamard]] e [[Charles Jean de la Vallée-Poussin|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 [[fattorizzazione|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à ==

[[File:Animation_Sieve_of_Eratosth-2Sieve of Eratosthenes animation.gif|thumb|300px|rightupright=1.4|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 [[numeri pari e dispari|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]].<ref>{{cita|Conway e Guy, ''Il libro dei numeri'', |p. 111|Conwayguy}}.</ref> 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.<ref>{{cita web|url=http://matematica-old.unibocconi.it/LangZac/primi.htm|titolo=Cosa sono i numeri primi|accesso=14 gennaio 2011|dataarchivio=22 luglio 2011|urlarchivio=https://web.archive.org/web/20110722060213/http://matematica-old.unibocconi.it/LangZac/primi.htm|urlmorto=sì}}</ref>

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

[[File:Prime rectangles.png|200px|thumb|left|Rappresentazione di 12 come rettangolo e tentativi di rappresentare 11 in questo modo.]]

Un metodo,antico algoritmo che discendeevita direttamentele dalladivisioni definizione,è peril verificare[[crivello sedi unEratostene|crivello]] numero(ossia ''nsetaccio'') èdi primo è controllare che non sia diviso dai numeri primi minori[[Eratostene di ''n''. Ad esempio, per provareCirene|Eratostene]] che 11 è primo, bastapiù osservare che non è diviso da 2precisamente, 3, 5 e 7 (che sono i primi minori di 11). Ildetermina l'[[crivello di Eratosteneinsieme]] è un algoritmo per generare i numeridei primi cheminori sio basauguali sua tale metodo''X''. PiùPer far precisamenteciò, perl'algoritmo determinareparte i primi nelldall'[[insieme]] dei numeri minorinaturali ocompresi ugualitra ad2 e ''X'', bastaed togliere dall'insieme tuttielimina i [[multiplo|multipli]] dei numeri primi minoriindividuati diin ''X''precedenza (esclusiperché inon primisono multipli di numeri più stessipiccoli);.<ref group="N">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.</ref> i numeri primi cercati saranno i numeri rimanenti al termine di queste esclusioni. In effetti, è possibile migliorare questo algoritmo fermandosi ada eliminare i multipli dei primi minori o uguali alla [[parte intera]] della [[radice quadrata|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,

:<math>c>\sqrt{X}\sqrt{X}=X.</math>

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

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

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.

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 ==

{{vedi anche|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 naturaleintero positivo diverso da uno1 può essere scomposto in fattori primi, e tale scomposizione è unica a meno dell'ordine dei fattori.

Ad esempio, 23244 si fattorizza come

Riga 48:

:<math>23244 = 2^2 \times 3 \times 13 \times 149 </math>

e ogni altra sua fattorizzazione in numeri primi è ottenuta da questa [[permutazione|permutando]] i fattori. Ad esempio, l'"ulteriore" fattorizzazione

:<math>23244=13\times 3\times 2\times 149\times 2</math>

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 "[[atomo|atomi]] dell'aritmetica".<ref>Ad esempio in du{{cita|Du Sautoy,| ''L'enigma dei numeri primi''.|Sautoy}}</ref>

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à]],<ref group="N">vedi [[#Generalizzazioni|il paragrafo sulle generalizzazioni]].</ref> 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à ==

Riga 61:

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:

{{quotecitazione|I numeri primi sono più di una qualsiasi assegnata moltitudine di numeri primi.|[[Euclide]], IX libro degli ''Elementi''.}}

La dimostrazione procede [[Dimostrazione per assurdo|per assurdo]]. Supponendo infatti che esistanoesista solo un numero finito di numeri primi ''p''<mathsub>1</sub>p_1,~p_2 ''p''₂,~ ...,~p_n ''p''<sub>''n''</mathsub>, si può considerare il numero <math>''q'' =p_1p_2\cdots p_n+''p''_{1</mathsub>''p''₂ ··· ''p''_''n'' + 1: questo numero è ovviamente maggiore di 1 e diverso da tutti i numeri primi ''p''<mathsub>p_i''i''</mathsub>. Ora, vi sono due possibilità per ''q'': può essere primo o composto. Se fosse primo avremmo però una contraddizione, perché abbiamo assunto che i ''p''<mathsub>p_i''i''</mathsub> siano tutti i numeri primi; se fosse invece composto, dovrebbe avere unaun fattore primo ''d'', che deve essere uno dei numeri primi ''p''<mathsub>p_i''i''</mathsub>. Ma allora ''d'' divide sia ''q'' chesia il prodotto ''p''<mathsub>1}''p''₂p_1p_2\cdots p_n··· ''p''<sub>''n''</mathsub> (essendo uno dei numeri primi), e quindi deve dividere la loro differenza <math>''q-p_1p_2\cdots'' p_n=− ''p''<sub>1</mathsub>''p''₂ ··· ''p''_''n'' = 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 ''p''<mathsub>p_1\cdots p_n+1</mathsub>''p''₂ ··· ''p''_''n'' + 1, cioè il prodotto dei primi ''n'' primi più 1 (detti [[numero di Euclide|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 ada essere composto è

:<math>2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13+1=30 031=59\cdot 509.</math>

Non è noto se in questa successione esistano infiniti numeri primi, anche se è stato [[congettura]]tocongetturato che sia così.<ref>{{cita web|lingua=en|url=http://mathworld.wolfram.com/EuclidNumber.html||autore= Eric W. Weisstein |sito=[[MathWorld]]|titolo=Euclid Number|accesso=2314 febbraiogennaio 2009|lingua=en2011}}</ref>

AltreMolte altre dimostrazioni sono state create nel corso dei secoli: [[Eulero]] dimostrò questo teorema a partire dalla [[divergenza]] della [[serie armonica]], [[Christian Goldbach|Goldbach]] attraverso i [[numero di Fermat|numeri di Fermat]], mentre [[Harry Furstenberg]] ne ideò una usando metodi didella [[topologia]].<ref>{{en}}{{cita pubblicazione|autore=Harry Furstenberg,|titolo=On Harrythe infinitude of primes|url=httphttps://www.jstorarchive.org/viewdetails/00029890sim_american-mathematical-monthly_1955-05_62_5/di991392page/99p17762/0|titolo=On the infinitude of primes353|rivista=[[American Mathematical Monthly|Amer. Math. Monthly]]|volume=62|numero=5|anno=1955|paginep=353|doi=10.2307/2307043| issn = 0002-9890 }}</ref>

Un teorema più forte, da cui si ricava facilmente l'infinità dei numeri primi, è quello che stabilisce che la [[serie (matematica){{TA|{{Sfrac|serie]] ¹/_|2}} + ^{{Sfrac|1/_|3}} + ^{{Sfrac|1/_|5}} + ^{{Sfrac|1/_|7}} + ^{{Sfrac|1/_|11}} + ...}}, formata dalla somma degli inversi dei numeri primi, [[serie divergente|diverge]],<ref>Vedi la [[dimostrazione della divergenza della serie dei reciproci dei primi|dimostrazione]].</ref> ede in particolare, usando la notazione [[O-grande]]:

:<math>\sum_{p\leq n} \frac{1}{p}=\ln \ln n+O(1).</math><ref>Vedi ad esempio in {{cita|Moser, ''An Introduction to the Theory of Numbers'', |p. 24|Moser}}.</ref>

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

Riga 81:

:<math>p_{n+1}<p_1p_2\cdots p_n.</math>

Tale disuguaglianza può essere migliorata: H. Bonse dimostrò nel 1907 ([[disuguaglianza di Bonse]]) che<ref>{{cita pubblicazione | autore = H. Bonse | anno = 1907 | titolo = "Üer eine bekannte Eigenschaft der Zahl 30 und ihre Verallgemeinerung" | rivista = Arch. Math. Phys | volume = 12 | paginepp = 292-295 }}</ref>

:<math>p_{n+1}^2 < p_1 p_2 ... p_n \,</math>

per ''n'' > 3. Su questa strada, è stato dimostrato che la disuguaglianza

:<math>p_{n+1}^k < p_1 p_2 ... p_n \,</math>

è verificata per ogni ''n'' > 2''k'' - 1.<ref>{{cita pubblicazione | autore = L. Panaitopol | anno = 2000 | titolo = "An inequality involving prime numbers" | rivista = Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. | volume = 11 | paginepp = 3-35 }}</ref>

== Distribuzione dei numeri primi ==

{{vedi anche|Teorema dei numeri primi}}

[[File:PrimeNumberTheorem.png|thumb|300pxupright=1.8|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'') èrisulta moltoessere di gran lunga migliore di quella con ''x'' / ln ''x'']]

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<nowiki>{{'</nowiki>}}''n''-esimo numero primo. Questo studio fu iniziatoincominciato verso la fine del [[XVIII secolo]] indipendentemente da [[Carl Friedrich Gauss|Gauss]] e da [[Adrien-Marie Legendre|Legendre]], che introdussero la funzione <math>\pi(x)</math> (detta [[funzione enumerativa dei primi]]) e congetturarono che essa fosse approssimativamente

:<math>\pi(x)\sim\frac{x}{\ln x}.</math><ref>Con questa espressione si intende che il [[limite (matematica)|limite]] del rapporto tra queste due espressioni tende a 1 quando ''x'' tende a infinito.</ref>

Il tentativo di dimostrare questa congettura attraversò tutto l'Ottocento; i primi risultati furono ottenuti tra il [[1848]] e il [[1859]] da [[Pafnutij L'vovič Čebyšëv|ChebyshevČebyšëv]], che dimostrò usando metodi puramente [[aritmetica|aritmetici]] che esistevano due costanti ''A'' e ''B'' tali che

:<math>A\leq \frac{\pi(x)}{\frac{x}{\ln x}} \leq B</math>

per ''x'' sufficientemente grande.<ref>{{cita|Ingham|p. 4 e 14|Ingham}}.</ref> Riuscì anche a provare che, se il [[limite (matematica)|limite]] del rapporto esiste, allora esso deve essere 1.<ref>{{cita|Ingham|p. 4 e 20|Ingham}}.</ref>

Una dimostrazione fu invece trovata nel [[1896]] da [[Jacques Hadamard|Hadamard]] e da [[Charles Jean de la Vallée-Poussin|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 [[Atle Selberg|Selberg]] e [[Paul Erdős|Erdős]]. Il teorema è oggi noto come [[teorema dei numeri primi]].

[[File:Primi-nlnn.svg|thumb|left|250pxupright=1.4|Confronto tra l<nowiki>{{'</nowiki>}}''n''-esimo numero primo (in blu) e ''n'' &middot;· ln ''n'' (in rosso), per ''n'' tra 0 e 10000.]]

[[Gauss]] aveva introdotto anche una stima più precisa, utilizzando la funzione [[logaritmo integrale]]:

:<math>\pi(x)\sim\frac{}{}\mathrm{Li}(x)=\int_2^x \frac{1}{\ln xu}\mathrm{d}xu.</math><ref>{{cita|Ingham|p. 3|Ingham}}.</ref>

Nel [[1899]] de la Vallée-Poussin dimostrò che l'errore che si commette approssimando <math>\pi(x)</math> in questo modo è

:<math> \pi(x)-\mathrm{Li}(x) = O \left(x \mathrm{e}^{-a\sqrt{\ln x}}\right)=O\left(\frac{x}{(\logln x)^m}\right)</math>

per una costante positiva ''a'' e ogni intero ''m''; tale risultato è stato leggermente migliorato nel corso degli anni.<ref>{{cita|Ingham, op. cit., |p. xi|Ingham}}.</ref> Inoltre, nel [[1901]] [[Helge von Koch|von Koch]] mostrò che se l'[[ipotesi di Riemann]] è vera, allora si ha la stima molto più precisa:

:<math> \pi(x) - \mathrm{Li}(x) = O\left(\sqrt x \ln x\right). </math><ref>{{cita|Ingham|p. 83 e 84|Ingham}}.</ref>

Una forma equivalente al teorema dei numeri primi è che ''p_n'', l<nowiki>{{'</nowiki>}}''n''-esimo numero primo, è ben approssimato da ''n'' ln(''n''). In effetti, ''p_n'' è strettamente maggiore di questo valore, come è stato dimostrato da [[J. Barkley Rosser]] nel [[1938]];<ref>{{cita pubblicazione | autore = J. B. Rosser | anno = 1938 | titolo = "The nth Prime is Greater than n ln n" | rivista = Proceedings of the London Mathematical Society | volume = 45 | paginepp = 21-44 }}</ref> questa disuguaglianza è stata migliorata fino ad arrivare, nel 1995, a

:<math>p_n>n(\ln n+\ln~\ln n -1),~</math>

per ''n'' ≥ 2.<ref>{{cita pubblicazione | autore = P. Dusart | anno = 1999 | titolo = "The k^(th) Prime is Greater than k(lnk+lnlnk-1) for k>=2." | url = https://archive.org/details/sim_mathematics-of-computation_1999-01_68_225/page/411 | rivista = Math. Comput | volume = 68 | paginepp = 411-415 }}</ref><ref>{{cita web|lingua=en|autore=Eric W. Weisstein|titolo=Rosser's Theorem|url=http://mathworld.wolfram.com/RossersTheorem.html|sito=MathWorld|accesso=14 gennaio 2011}}</ref>

=== Intervalli tra i numeri primi ===

[[ File:Anzahl_Primzahl-ZwillingspaarePrimigemelli.png svg|230pxupright=1.4|thumb|La distibuzionedistribuzione dei primi gemelli per ''n''≤1000≤100&nbsp;000]]

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 un numero pari 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 ''[[numeri primi gemelli|''gemelli'']]'': adcon l'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 [[congettura]]tocongetturato 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]].

È facile invece mostrare che questa differenza può essere grande a piacere: dato un intero ''N'', ede indicando con ''N!'' il suo [[fattoriale]] (cioè il prodotto di tutti i numeri compresi tra 1 ede ''N''), i numeri

:<math>(N+1)!+2,~(N+1)!+3,\cdots,(N+1)!+N+1</math>

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

:<math>6!+2=722=2\times 361</math>

:<math>6!+3=723=3\times 241</math>

Riga 131:

:<math>6!+5=725=5\times 145</math>

:<math>6!+6=726=6\times 121</math>

mentre il valore successivo, 6!+7=727, è primo.<ref group="N">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.</ref> Si noti comunque che esistono modi più "efficienti" per costruire intervalli senza numeri primi; ad esempio invece di (''N'' + 1)! + 1 si può considerare il prodotto dei numeri primi minori di ''N'' + 2.

Dal teorema dei numeri primi discende facilmente che l'intervallo [[Valore atteso|atteso]] tra due numeri primi consecutivi ''p_n'' e ''p''_''n''+1 ha lunghezza ln(''p_n''); tuttavia questi intervalli sono talvolta molto più grandi e talvolta molto più piccoli. Sugli intervalli corti, la [[congettura dei numeri primi gemelli|congettura dei primi gemelli]] afferma esattamente che l'intervallo è il minimo possibile infinite volte. Questa congettura è tuttora aperta, ma grazie al lavoro di [[Zhang Yitang]] (annunciato nel 2013, e basato sull'approccio di [[Daniel Goldston|Goldston]], [[János Pintz|Pintz]] e [[Cem Yıldırım|Yıldırım]]<ref>{{cita pubblicazione | autore = D.A. Goldston|autore2=J. Pintz|autore3=Y. Yilidrim| titolo = Primes in tuples. II. | rivista = Acta. Math. | anno = to appear |url = http://www.renyi.hu/~pintz/0710.2728.pdf|accesso=14 gennaio 2011}}</ref>) e ai successivi contributi di [[James Maynard]] e di un [[progetto Polymath]], è noto che esistono infiniti numeri primi consecutivi la cui differenza è minore di 246.<ref>{{Cita pubblicazione|cognome=McKee|nome=Maggie|titolo=First proof that infinitely many prime numbers come in pairs|rivista=Nature|data=14 maggio 2013|url=https://www.nature.com/news/first-proof-that-infinitely-many-prime-numbers-come-in-pairs-1.12989|issn=0028-0836}}</ref><ref>{{Cita pubblicazione | url = http://annals.math.princeton.edu/wp-content/uploads/YitangZhang.pdf | titolo = Bounded gaps between primes | nome = Yitang | cognome = Zhang | rivista = Annals of Mathematics | editore = Princeton University and the Institute for Advanced Study | accesso = 21 maggio 2013 | dataarchivio = 12 giugno 2013 | urlarchivio = https://web.archive.org/web/20130612175256/http://annals.math.princeton.edu/wp-content/uploads/YitangZhang.pdf | urlmorto = sì }}</ref><ref>{{Cita web|cognome=Tao|nome=Terence|wkautore=Terence Tao|url=https://terrytao.wordpress.com/2013/06/03/the-prime-tuples-conjecture-sieve-theory-and-the-work-of-goldston-pintz-yildirim-motohashi-pintz-and-zhang/|titolo=The prime tuples conjecture, sieve theory, and the work of Goldston-Pintz-Yildirim, Motohashi-Pintz, and Zhang|data=4 giugno 2013}}</ref><ref>{{Cita pubblicazione | url = https://link.springer.com/article/10.1186%2Fs40687-014-0012-7 | titolo = Variants of the Selberg sieve, and bounded intervals containing many primes| nome = DHJ | cognome = Polymath| rivista = Research in the Mathematical Sciences | editore = Springer International Publishing | accesso=13 febbraio 2015}}</ref>

Dal teorema dei numeri primi discende facilmente che l'intervallo [[Valore atteso|atteso]] tra due numeri primi consecutivi ha lunghezza ln(''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

:<math>\liminf_{n\rightarrow\infty}\frac{p_{n+1}-p_n}{\sqrt{\log p_n}(\log\log p_n)^2}=0,</math><ref>{{cita pubblicazione | autore = D.A. Goldston, J. Pintz, Y. Yilidrim| titolo = "Primes in tuples. II." | rivista = Acta. Math. | anno = to appear |url = http://www.renyi.hu/~pintz/0710.2728.pdf}}</ref>

Sul problema opposto, degli intervalli lunghi, ci si aspetta che tali intervalli siano di ordine ln² ''p_n'', o, più precisamente, 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

:<math>0<\limsup_{n\rightarrow\infty}\frac{p_{n+1}-p_{n}}{\ln^2n}\ll1,</math><ref name = Pintz>{{cita web| autore = J. Pintz| titolo = Landau's problems on primes. | url = http://www.renyi.hu/~pintz/pjapr.pdf|accesso=14 gennaio 2011}}</ref>

mentre i migliori risultati dimostrati sono

:<math>0<\limsup_{n\rightarrow\infty}\frac{p_{n+1}-p_{n}}{\log^2n}\ll1.</math><ref name = Pintz>{{citaweb | autore = J. Pintz| titolo = Landau's problems on primes. | url = http://www.renyi.hu/~pintz/pjapr.pdf}}</ref>

:<math>\limsup_{n\rightarrow\infty}\frac{p_{n+1}-p_{n}}{\ln p_n(\ln\ln p_n)(\ln\ln\ln\ln p_n)/\ln\ln\ln p_n}> 0</math><ref>{{cita pubblicazione | autore = K. Ford | autore2 = B. Green | autore3 = S. Konyagin| autore4 = J. Maynard | autore5= T. Tao| titolo = Long gaps between consecutive prime numbers | sito = https://arxiv.org/abs/1412.5029 | anno = 2015}}</ref>

In questo caso, i migliori risultati provati sono

:<math>\limsup_{n\rightarrow\infty}\frac{(p_{n+1}-p_{n})(\log\log\log p_n)^2}{\log p_n(\log\log p_n)(\log\log\log\log p_n)}\geq 2e^\gamma</math><ref name = Pintz />

e

:<math>p_{n+1}-p_n=O\left(p_n^{\frac{21}{40}}\right),</math><ref>{{cita namepubblicazione | autore = R. C. Baker|autore2=G. Harman|autore3=J. Pintz | titolo = The difference between consecutive primes, II. | rivista = Proc. London Math. Soc. | anno = 2001| numero = 3|volume=83}}</ref>

dovuti rispettivamente a [[Kevin Ford|Ford]], [[Ben Green|Green]], [[Sergej Konjagin|Konjagin]], Maynard e [[Terence Tao|Tao]] e a Pintz.

dovuti entrambi a Pintz.

Un altro risultato classico, seppur più debole di quelli appena riportati, è il [[postulato di Bertrand]] (dimostratoche nelin [[1850]]realtà è un teorema, essendo stato dimostrato da [[Pafnutij L'vovič Čebyšëv|ChebyshevČebyšëv]] nel 1850),. cheEsso afferma che, per ogni ''n'', esiste sempre un primo tra ''n'' e 2''n''. Un'interessante conseguenza di questo risultato è che è che ''p''<mathsub>p_{''n''+1}<2p_n/sub> < 2''p''<sub>''n''</mathsub>; considerando inoltre che ''p''₁ = 2 si deduce facilmente che per ogni ''n'' vale la disuguaglianza

:<math>p_n<2^n.</math>

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

:<math>\sqrt{p_{n+1}}-\sqrt{p_n}<1.</math>

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 ''n''² e (''n'' + 1)² giace sempre almeno un primo o un [[semiprimo]], dovuta a [[Chen Jingrun]],<ref>{{cita pubblicazione | autore = J. R. Chen | anno = 1975 | titolo = "On the Distribution of Almost Primes in an Interval." | rivista = Sci. Sinica | volume = 18 | paginepp = 611-627 }}</ref> e il risultato di Baker, Harman e Pintz riportato sopra.

== Rapporti con gli altri campi della matematica ==

Riga 162 ⟶ 160:

=== Funzioni aritmetiche ===

Le [[funzione aritmetica|funzioni aritmetiche]], ossia le funzionefunzioni definite sugli interi e a valori nei [[numero complesso|numeri complessi]], rivestono un ruolo cruciale nella [[teoria dei numeri]]. In modo particolare, tra queste le più importanti sono le [[funzione moltiplicativa|funzioni moltiplicative]], ovvero quelle funzioni ''f'' in cui, per ogni coppia (''a'',''b'') di numeri [[Interi coprimi|coprimi]], si ha

:<math>f(ab)=f(a)f(b).\!</math>

Esempi di funzioni moltiplicative sono la [[funzione phiφ di Eulero]], che ada ''n'' associa il numero degli interi che sono al contempo minori e coprimi con ''n'', e le funzioni [[Funzione tau sui positivi|divisore]] e [[funzione sigma|sigma]], che ada ''n'' associano rispettivamente il numero dei suoi divisori e la loro somma. Il valore di tali funzioni nelle potenze dei primi è

*[[ funzione phiφ di Eulero]]: <math>\operatorname{\varphi}(p^m)=p^nm-p^{nm-1},</math>

*[[Funzione tau sui positivi|funzione divisore]]: <math>\operatorname{d}(p^m)=m+1,</math>

*[[ funzione sigma]]: <math>\operatorname{\sigma}(p^m)=1+p^1+p^2+p^3+\cdots+p^m.</math>

Grazie alla proprietà che le definisce, le funzioni aritmetiche si possono facilmente calcolare conoscendo il valore che esse assumono nelle [[Potenza (matematica)|potenze]] dei primi. Infatti, dato un intero ''n'' di fattorizzazione

Riga 180 ⟶ 178:

:<math>f(n)=f(p_1^{q_1})\cdots f(p_a^{q_a})</math>

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 ada una formula generale. Ad esempio, per conoscere il valore della funzione phiφ di Eulero su ''n'' = 450 = 2×3²×5² è sufficiente calcolare

:<math>\operatorname{\sigmavarphi}(450)=\operatorname{\sigmavarphi}(2)\cdot\operatorname{\sigmavarphi}(3^2)\cdot\operatorname{\sigmavarphi}(5^2)=(2-1)\cdot(9-3)\cdot(25-5)=120.</math>

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 formale di potenze|serie formali di potenze]]. Data una funzione moltiplicativa ''f'' e un primo ''p'', la serie di Bell di ''f'' rispetto a ''p'' è:

Riga 192 ⟶ 190:

:<math>f_p(x)=\sum_{n=0}^\infty f(p)^n x^n=\frac{1}{1-f(p)x}.</math>

=== NumeriAritmetica ''p''-adicimodulare ===

{{vedi anche|Numero p-adico}}

Nell'[[aritmetica modulare]] i numeri primi svolgono un ruolo molto importante: l'[[anello (algebra)|anello]] <math>\mathbb{Z}/n\mathbb{Z}</math> delle classi di resto è infatti un [[campo (matematica)|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.

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 (matematica)|norma]] sui [[numero razionale|numeri razionali]] <math>\mathbb{Q}</math> 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". [[spazio completo|Completando]] il campo dei numeri razionali rispetto alla [[metrica (matematica)|metrica]] indotta da tale norma, si ottiene un campo, indicato con <math>\mathbb{Q}_p</math>, che "estende" i [[numero razionale|numeri razionali]] in un modo diverso dai [[numero reale|numeri reali]]. Gli elementi di tale campo sono detti '''numeri ''p''-adici'''. Tali numeri si possono anche costruire come [[limite proiettivo]] degli anelli <math>\mathbb{Z}/p\mathbb{Z},~\mathbb{Z}/p^2\mathbb{Z},~ \mathbb{Z}/p^3\mathbb{Z}\ldots</math>.

Anche l'esistenza di una [[Radice primitiva modulo n|radice primitiva]] dell'anello <math>\mathbb{Z}/n\mathbb{Z}</math> è legata ai numeri primi: questa infatti esiste solamente se ''n'' è un numero primo, 1, 2, 4 oppure un numero nella forma <math>p^n</math> o <math>2p^n</math>, dove ''p'' è un primo dispari.<ref>{{cita|Apostol|capitolo 10|Apostol}}.</ref>

=== Teoria dei gruppi ===

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

I numeri primi hanno un ruolo centrale anche nell'[[algebra astratta|algebra]]. Nella [[teoria dei gruppi]], un [[gruppo (matematica)|gruppo]] in cui ogni elemento ha [[Glossario di teoria dei gruppi#Definizioni di base|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 è [[gruppo finito|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 [[isomorfismo|isomorfismi]]): il [[gruppo di Prüfer|''p''-gruppo di Prüfer]].

:<math>a^p\equiv a\mod p.</math>

È noto che i ''p''-gruppi hanno un [[centro di un gruppo|centro]] non banale, e di conseguenza non possono essere [[gruppo semplice|semplici]] (a parte il gruppo con ''p'' elementi); se il gruppo è finito, inoltre, tutti i [[sottogruppo normale|sottogruppi normali]] intersecano il centro in modo non banale.

Equivalentemente, per ogni primo ''p'' e ogni intero ''a'' [[interi coprimi|coprimo]] con ''p'', si ha

Tutti i gruppi con un numero primo di elementi sono [[gruppo ciclico|ciclici]] e dunque [[gruppo abeliano|abeliani]]; anche ogni gruppo di ordine ''p''² è abeliano. Inoltre, ogni gruppo abeliano finito è isomorfo al [[prodotto diretto]] di un numero finito di ''p''-gruppi ciclici.

:<math>a^{p-1}\equiv 1\mod p.</math>

Il [[teorema di Cauchy (teoria dei gruppi)|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 ''p^m'', per ogni ''p^m'' che divide ''n''.

Questa proprietà può essere usata per verificare se un numero ''non'' è primo, infatti se ''n'' è tale che

=== Teoria degli anelli e teoria dei campi ===

:<math>a^{n}\not\equiv a\mod n</math>

Nella [[teoria degli anelli]], la [[caratteristica (algebra)|caratteristica]] di un [[dominio d'integrità]] ''D'' è 0 oppure un numero primo. Per un [[Campo (matematica)|campo]] ''F'', che è un particolare tipo di dominio di integrità, la caratteristica determina il [[Campo (matematica)#Sottocampi e estensione di campi|sottocampo fondamentale]] di ''F'': se essa è diversa da 0, e dunque è un numero primo, allora tale sottocampo è isomorfo al campo delle classi di resto <math>\mathbb{Z}/p\mathbb{Z}</math>.

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 [[numero di Carmichael|numeri di Carmichael]] (il più piccolo dei quali è 561), che verificano questa proprietà per ogni ''a'' pur non essendo primi. Nel 1994, [[William Robert Alford]], [[Andrew Granville]] e [[Carl Pomerance]] hanno dimostrato che vi sono infiniti numeri di tale tipo.<ref>{{cita pubblicazione | autore = W. R. Alford|autore2=A. Granville|autore3=C. Pomerance | anno = 1994 | titolo = There are Infinitely Many Carmichael Numbers. | url = https://archive.org/details/sim_annals-of-mathematics_1994-05_139_3/page/703| rivista = Annals of Mathematics | volume = 139 | pp = 703-722 }}</ref>

Si mostra poi che tutti i [[campo finito|campi finiti]] formano uno [[spazio vettoriale]] sul campo <math>\mathbb{Z}/p\mathbb{Z}</math>, 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 [[isomorfismo|isomorfi]]; in particolare, ogni campo con un numero primo ''p'' di elementi coincide con <math>\mathbb{Z}/p\mathbb{Z}</math>, mentre ogni campo con ''pⁿ'' elementi è un'[[estensione di Galois]] di un campo con ''p'' elementi.

=== Numeri ''p''-adici ===

Tra le estensioni dei numeri razionali, un ruolo importante è svolto dalle [[estensione ciclotomica|estensioni ciclotomiche]], ossia da quei campi che si possono ottenere aggiungendo a <math>\mathbb{Q}</math> le [[Radice dell'unità|radici ''n''-esime dell'unità]], per un qualche numero naturale ''n''. Il [[Grado (matematica)|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]]

{{vedi anche|Numero p-adico}}

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 (matematica)|norma]] sui [[numero razionale|numeri razionali]] <math>\mathbb{Q}</math> 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". [[spazio completo|Completando]] il campo dei numeri razionali rispetto alla [[Distanza (matematica)|metrica]] indotta da tale norma, si ottiene un campo, indicato con <math>\mathbb{Q}_p</math>, che "estende" i [[numero razionale|numeri razionali]] in un modo diverso dai [[numero reale|numeri reali]]. Gli elementi di tale campo sono detti '''numeri ''p''-adici'''. Tali numeri si possono anche costruire come [[Limite inverso|limite proiettivo]] degli anelli <math>\mathbb{Z}/p\mathbb{Z},~\mathbb{Z}/p^2\mathbb{Z},~ \mathbb{Z}/p^3\mathbb{Z}\ldots</math>.

:<math>P(x)=x^{n-1}+x^{n-2}+\cdots+x^2+x+1</math>

=== Teoria dei gruppi ===

è [[polinomio irriducibile|irriducibile]] tra i polinomi a coefficienti [[numero razionale|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

I numeri primi hanno un ruolo centrale anche nell'[[algebra astratta|algebra]]. Nella [[teoria dei gruppi]], un [[gruppo (matematica)|gruppo]] in cui ogni elemento ha [[Glossario di teoria dei gruppi#Definizioni di base|ordine]] la potenza di un primo ''p'' è detto ''[[Gruppo primario|p-gruppo]]'' o ''gruppo primario''. Tra i [[gruppo finito|gruppi finiti]], i ''p''-gruppi sono tutti e soli i gruppi la cui [[cardinalità]] è la potenza di un primo; un esempio di ''p''-gruppo infinito è il [[gruppo di Prüfer|''p''-gruppo di Prüfer]].

:<math>x^9+x^8+\cdots+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).</math>

È noto che i ''p''-gruppi hanno un [[centro di un gruppo|centro]] non banale, e di conseguenza non possono essere [[gruppo semplice|semplici]] (a parte il gruppo con ''p'' elementi); se il gruppo è finito, inoltre, tutti i [[sottogruppo normale|sottogruppi normali]] intersecano il centro in modo non banale.

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<nowiki>'</nowiki>''n''-esimo [[polinomio ciclotomico]].

Tutti i gruppi con un numero primo di elementi sono [[gruppo ciclico|ciclici]] e dunque [[gruppo abeliano|abeliani]]; anche ogni gruppo di ordine ''p''² è abeliano. Inoltre, ogni gruppo abeliano finito è isomorfo al [[prodotto diretto]] di un numero finito di ''p''-gruppi ciclici.

=== Aritmetica modulare ===

Il [[teorema di Cauchy (teoria dei gruppi)|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 ''p^m'', per ogni ''p^m'' che divide ''n''.

Anche nell'[[aritmetica modulare]] i numeri primi svolgono un ruolo molto importante: l'[[anello (algebra)|anello]] <math>\mathbb{Z}/n\mathbb{Z}</math> delle classi di resto è infatti un [[campo (matematica)|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.

=== Teoria degli anelli e teoria dei campi ===

Anche l'esistenza di una [[radice primitiva]] dell'anello <math>\mathbb{Z}/n\mathbb{Z}</math> è legata ai numeri primi: questa infatti esiste solamente se ''n'' è un numero primo, 1, 2, 4 oppure un numero nella forma <math>p^n</math> o <math>2p^n</math>, dove ''p'' è un primo dispari.<ref>Apostol, op. cit., capitolo 10.</ref>

Nella [[teoria degli anelli]], la [[caratteristica (algebra)|caratteristica]] di un [[dominio d'integrità]] ''D'' è 0 oppure un numero primo. Per un [[Campo (matematica)|campo]] ''F'', che è un particolare tipo di dominio di integrità, la caratteristica determina il [[Campo (matematica)#Sottocampi e estensione di campi|sottocampo fondamentale]] di ''F'': se essa è diversa da 0, e dunque è un numero primo, allora tale sottocampo è isomorfo al campo delle classi di resto <math>\mathbb{Z}/p\mathbb{Z}</math>.

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

Si mostra poi che tutti i [[campo finito|campi finiti]] formano uno [[spazio vettoriale]] sul campo <math>\mathbb{Z}/p\mathbb{Z}</math>, 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 [[isomorfismo|isomorfi]]; in particolare, ogni campo con un numero primo ''p'' di elementi coincide con <math>\mathbb{Z}/p\mathbb{Z}</math>, mentre ogni campo con ''pⁿ'' elementi è un'[[estensione di Galois]] di un campo con ''p'' elementi.

:<math>a^p\equiv a\mod p.</math>

Tra le estensioni dei numeri razionali, un ruolo importante è svolto dalle [[estensione ciclotomica|estensioni ciclotomiche]], ossia da quei campi che si possono ottenere aggiungendo a <math>\mathbb{Q}</math> le [[Radice dell'unità|radici ''n''-esime dell'unità]], per un qualche numero naturale ''n''. Il [[Estensione di campi#Struttura lineare|grado]] di queste estensioni è strettamente legato alla primalità di ''n''. Infatti esso è ''n'' − 1 se e solo se ''n'' è primo: tale proprietà è equivalente al fatto che il [[polinomio]]

Equivalentemente, per ogni primo ''p'' e ogni intero ''a'' [[interi coprimi|coprimo]] con ''p'', si ha:

:<math>aP(x)=x^{pn-1}+x^{n-2}+\equiv cdots+x^2+x+1\mod p.</math>

è [[polinomio irriducibile|irriducibile]] tra i polinomi a coefficienti [[numero razionale|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 a una scomposizione. Ad esempio, se ''n'' = 10, prendendo ''a'' = 2 e ''b'' = 5, ''P''(''x'') si può scomporre come

Questa proprietà può essere usata per verificare se un numero ''non'' è primo, infatti se ''n'' è tale che

:<math>x^9+x^8+\cdots+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).</math>

:<math>a^{n}\not\equiv a\mod n</math>

Per dimostrare l'inverso, si può usare 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]].

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 [[numero di Carmichael|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.<ref>{{cita pubblicazione | autore = W. R. Alford, A. Granville e C. Pomerance | anno = 1994 | titolo = "There are Infinitely Many Carmichael Numbers." | rivista = Annals of Mathematics | volume = 139 | pagine = 703-722 }}</ref>

== Polinomi e progressioni aritmetiche ==

È stato dimostrato da [[Adrien-Marie Legendre|Legendre]] alla fine del [[XVIII secolo|Settecento]]<ref>{{cita|Boyer, ''Storia della matematica'', |p. 565|Boyer}}.</ref> 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.<ref>{{cita libro|cognome=Stark|nome=Harold|titolo=An introduction to number theory|editore=The MIT Press|città=Cambridge| edizione=10|anno=1998|idp=61|ISBN =0-262-69060-8}}</ref>

Alcuni polinomi sembrano assumere valori primi "più spesso" degli altri: ad esempio [[Eulero]] notò che il polinomio di secondo grado <math>n^2+n+41</math> 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,<ref>{{cita|Devlin, ''Dove va la matematica'', |p. 73|Devlin}}.</ref> 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]] <math>ax^2+bxy+cy^2</math> (a patto che ''a'', ''b'' e ''c'' siano coprimi e che la forma non sia il quadrato di un polinomio di primo grado),<ref>[[Harold {{cita|Davenport]], ''Aritmetica superiore'', |p. 33|Davenport}}.</ref> mentre nel [[1998]] [[John Friedlander]] e [[Henryk Iwaniec]] lo provarono per il polinomio di quarto grado <math>x^2+y^4</math>.<ref>{{en}}{{cita pubblicazione|autore = [[John Friedlander]] e [[Henryk Iwaniec]]|titolo = The polynomial ''X''² + ''Y''⁴ captures its primes|rivista = Annals of Mathematics|volume = 148|data = 1998|paginepp = 945–1040945-1040|url = http://www.emis.ams.org/journals/Annals/148_3/fried1.pdf|doi = 10.2307/121034|accesso = 14 gennaio 2011|urlarchivio = https://web.archive.org/web/20170808044347/http://www.emis.ams.org/journals/Annals/148_3/fried1.pdf|dataarchivio = 8 agosto 2017|urlmorto = sì}}</ref>

[[File:Primi=3mod4.svg|thumb|300pxupright=1.4|Frazione dei numeri primi [[aritmetica modulare|congrui]] a 3 modulo 4.]]

A differenza di quanto accade per i polinomi di grado più alto, [[Johann Peter Gustav Lejeune Dirichlet|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, ogniuna [[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 analiticaTeoria dei numeri analitica]].<ref>{{cita|Apostol, ''Introduction to Analytic Number Theory'', |p. 7|Apostol}}.</ref>

È noto inoltre che, se ''n'' e ''k'' sono coprimi, il rapporto tra ''M'' e i primi minori di ''M'' che sono congrui a ''k'' [[aritmetica modulare|modulo]] ''n'' tende a <math>1/\phi(n)</math> per ''M'' che tende all'infinito, ovvero i primi tendono a dividersi equamente tra le <math>\phi(n)</math> progressioni di ragione ''n'' che contengono più di un primo.<ref>{{cita|Apostol, ''Introduction to Analytic Number Theory'', |p. 149|Apostol}}.</ref>

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]]).<ref>{{cita pubblicazione | autore = [[Ben Green]] e [[Terence Tao]] | anno = 2008 | titolo = The primes contain arbitrarily long arithmetic progressions | rivista = [[Annals of Mathematics]] | volume = 167 | paginepp = 481-547 | url = http://annals.math.princeton.edu/issuesannals/2008/March2008167-2/GreenTaoannals-v167-n2-p03-p.pdf | accesso = 23 febbraio 2009 | urlmorto = sì | urlarchivio = https://web.archive.org/web/20100620180200/http://annals.princeton.edu/annals/2008/167-2/annals-v167-n2-p03-p.pdf | dataarchivio = 20 giugno 2010 }} [https://arxiv.org/abs/math/0404188 Su Arxiv]</ref> Tale risultato è stato migliorato nel [[2006]] per includere anche le progressioni polinomiali; più precisamente è stato dimostrato che, dati dei polinomi ''P''₁, ...,''P''_''m'' a coefficienti interi, esistono infiniti interi ''a'' e ''m'' tali che ''a''+''P''₁(''n''), ..., ''a''+''P''_''m''(''n'') sono contemporanemanentecontemporaneamente primi per 1 ≤ ''n'' ≤ ''m''.<ref>{{cita web|autore=[[Terence Tao]] e [[Tamar Ziegler]]|url=http://arXiv.org/abs/math.NT/0610050|titolo=The primes contain arbitrarily long polynomial progressions|accesso=234 febbraiosettembre 2009|lingua=en}}</ref>

Tali teoremi non sono tuttavia ''costruttivi'', ovvero non permettono di determinare esplicitamente delle progressioni arbitrariamente lunghe.; Lala più lunga sequenza di primi (attualmente conosciuta) che sono termini consecutivi di una progressione aritmetica è composta da 2526 numeri.<ref>{{cita web|autore=[[Jens Kruse Andersen]]|url=http://hjem.get2netprimerecords.dk/jka/math/aprecords.htm|titolo=Primes in Arithmetic Progression Records|accesso=1528 agostogiugno 20082014|lingua=en}}</ref> È stato anche congetturato che esistano sequenze arbitrariamente lunghe di questo tipo tali che tra due termini della progressione non ci siano altri numeri primi., e Lala più lunga sequenza di primi di questo tipo finora trovata comprende 10 termini.<ref>{{cita pubblicazione | autore = H. Dubner, |autore2=T. Forbes, |autore3=N. Lygeros, |autore4=M. Mizony, |autore5=H. Nelson, |autore6=P. Zimmermann | anno = 2002 | titolo = "Ten consecutive primes in arithmetic progression" | rivista = [[Mathematics of Computation]] | volume = 71 | paginepp = 1323-1328 | url = http://www.ams.org/mcom/2002-71-239/S0025-5718-01-01374-6/home.html | accesso = 1114 gennaio 20092011 }}</ref><ref>{{cita web|autore=[[Jens Kruse Andersen]]|url=http://primerecords.dk/cpap.htm|titolo=The Largest Known CPAP's|accesso=28 giugno 2014}}</ref>

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 4''k''+1 e quelli nella forma 4''k''+3. Il [[teorema di Fermat sulle somme di due quadrati]] asserisce che i primi che possono essere scritti come somma di due [[numero quadrato perfetto|quadrati]] sono tutti e soli quelli del primo gruppo. Un'importante riformulazione di questo teorema è che un primo è scomponibile nell'[[anello (algebra)|anello]] degli [[Intero gaussiano|interi di Gauss]] se e solo se è della forma 4''k''+1.

== Problemi additivi ==

[[File:Goldbach-1000000.png |270pxupright=1.6|thumb|Il numero di modi con cui un numero ''n'' si può scrivere come somma di due primi per ''n''≤1 &nbsp;000 &nbsp;000]]

Per la loro definizione, i numeri primi sono intrinsecamente legati all'[[Operazione binaria|operazione]] di moltiplicazione. Tuttavia, sono di grande interesse anche alcuni problemi riguardanti loro proprietà [[Addizione|additive]].

Il più famoso di questi è senza dubbio la [[congettura di Goldbach|congettura]] proposta da [[Christian Goldbach]] nel [[XVIII secolo|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

:&nbsp; 4 = 2 + 2

:&nbsp; 6 = 3 + 3

Riga 270 ⟶ 268:

:14 = 3 + 11 = 7 + 7,

e tramite l'uso di computer è stata controllata anche per tutti gli ''n'' minori di 102×10¹⁸.<ref>{{cita web|autore=Tomás Oliveira e |autore2=Silva|url=http://www.ieeta.pt/~tos/goldbach.html|titolo=Goldbach conjecture verification|accesso=2314 febbraiogennaio 20092011|lingua=en}}</ref>

Alla congettura di Goldbach ne è legata un'[[congettura debole di Goldbach|altra]], più debole mae anch'essaora indimostratadimostrata, che afferma che ogni numero dispari è la somma di tre numeri primi. Questa ''ex''-congettura è comunemente nota con il nome di [[congettura debole di Goldbach]].

Mentre la congettura di Goldbach sembra molto lontana dall'essere risolta, la seconda ha conosciuto diversi progressi nel corso degli anni, culminati nella dimostrazione completa data da [[Harald Helfgott]] nel 2013. In precedenza, risultati significativi erano stati ottenuti da [[Godfrey Harold Hardy|Hardy]] e [[John Edensor Littlewood|Littlewood]], che nel 1923 provarono che l'[[ipotesi di Riemann generalizzata]] implica che ogni numero dispari ''[[sufficientemente grande]]'' è la somma di tre primi,<ref>{{cita pubblicazione|autore= G. H. Hardy|autore2=J. E. Littlewood|anno=1923|titolo=Some problems of ‘Partitio numerorum’; III: On the expression of a number as a sum of primes|rivista=Acta Math.|volume=44}}</ref> e da [[Ivan Matveevič Vinogradov|Ivan Vinogradov]] che nel 1937 dimostrò che l'assunzione dell'ipotesi di Riemann non è necessaria.<ref>{{cita libro | autore = H. Davenport|wkautore=Harold Davenport| titolo = Multiplicative Number Theory | ed=3 | editore = Springer | città = Berlino |anno = 2000 |capitolo=26. Sums of three primes|ISBN=978-0-387-95097-6}}</ref> Per completare la dimostrazione mancavano quindi solo un numero finito di numeri dispari da controllare<ref>Nel lavoro originale di Vinogradov tale numero non era [[Risultati effettivi in teoria dei numeri|effettivamente calcolabile]] ma questo problema è stato superato qualche anno dopo dal suo studente K. Borozdin. Si veda {{Cita pubblicazione|nome=Terence|cognome=Tao|wkautore=Terence Tao|anno=2011|titolo=An Invitation to Mathematics: From Competitions to Research|editore=Springer|pp=1-7|doi=10.1007/978-3-642-19533-4_1|contributo=Structure and Randomness in the Prime Numbers|curatore-nome1=Dierk|curatore-cognome1=Schleicher|curatore-nome2=Malte|curatore-cognome2=Lackmann}}</ref>, ma tale numero era ben al di là delle capacità computazionali dei moderni computer. Nel 2013, Helfgott introdusse diverse innovazioni all'interno della dimostrazione di Vinogradov, riuscendo ad abbassare notevolmente il numero di potenziali eccezioni a un numero effettivamente controllabile da un computer e quindi a completare la dimostrazione.

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.<ref>O. Ramaré, "On Schnirelmann's constant," ''Ann. Sc. Norm. Super. Pisa'', 22:4 (1995) 645-706.</ref> 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.<ref>{{cita pubblicazione | autore = Deshouillers, Effinger, Te Riele e Zinoviev | anno = 1997 | titolo = "A complete Vinogradov 3-primes theorem under the Riemann hypothesis" | rivista = Electronic Research Announcements of the American Mathematical Society | volume = 3 | pagine = 99-104 | url = http://www.ams.org/era/1997-03-15/S1079-6762-97-00031-0/S1079-6762-97-00031-0.pdf | accesso = 11 gennaio 2009 }}</ref>

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 ''p_n'' è l<nowiki>{{'</nowiki>}}''n''-esimo numero primo, allora almeno uno tra ''p_n'', ''p_n''- − 1 e ''p_n'' +1 1 può essere scritto come

:<math>\pm 2\pm 3\pm 5\cdots\pm p_{n-1}</math>

Riga 282 ⟶ 280:

scegliendo opportunamente i segni "più" e "meno".

Problemi additivi sono considerati anche i già citati [[teorema di Green-Tao]] sulle progressioni aritmetiche, la [[congettura dei numeri primi gemelli|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:<ref>{{cita web|autore=[[Enrico Bombieri]]|url=https://claymath.org/millennium/Riemann_Hypothesis/riemann.pdf|titolo=Problems of the Millennium: The Riemann Hypothesis|accesso=14 gennaio 2011|urlmorto=sì|urlarchivio=https://web.archive.org/web/20110111163814/http://www.claymath.org/millennium/Riemann_Hypothesis/riemann.pdf|dataarchivio=11 gennaio 2011}}</ref><ref>{{cita|Devlin|p. 211|Devlin}}.</ref> era uno dei ventitré [[problemi di Hilbert]], enunciati nel [[1900]], ed essendo ancora insoluto è stato ripropostoinserito fratra i sette [[problemi per il millennio]] nel [[2000]]. Nella sua formulazione originale, tale ipotesi riguarda il posizionamento degli zeri [[numero complesso|complessi]] della [[funzione zeta di Riemann]],: e quindi non è immediatamente chiarononostante il suo legame con i numeri primi; tuttavianon sia immediatamente chiaro, è stato dimostratoprovato che la veritàsua dell'ipotesi di Riemanndimostrazione avrebbe come conseguenza un notevole miglioramento della comprensione delladei distribuzionenumeri asintoticaprimi. deiIn numeriparticolare, se l'ipotesi di Riemann fosse vera, i primi sarebbero distribuiti nel modo più regolare possibile.<ref>{{Cita libro | cognome=Patterson | nome=S. J. | titolo=An introduction to the theory of the Riemann zeta-function | url=https://archive.org/details/introductiontoth0000patt | editore=[[Cambridge University Press]] | anno=1988|p=75 | ISBN=978-0-521-33535-5 }}</ref>

Altri due problemi aperti molto famosi sono le già citate congetture di [[congettura di Goldbach|Goldbach]], dei [[congettura dei numeri primi gemelli|primi gemelli]] e di [[congettura di Legendre|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 ''n²'' + 1<ref>{{OEIS|A002496}}</ref>, 2^''n'' - 1 ([[numero primo di Mersenne|primi di Mersenne]], [[OEIS:000043A000043]]), ''n''! + 1 e ''n''! - 1 ([[primo fattoriale|primi fattoriali]], sequenze [[OEIS:002981A002981]] e [[OEIS:117141A117141]]), o che esistano infiniti primi nella [[successione di Fibonacci]].<ref>{{cita web|lingua=en|autore=Chris Caldwell|url=http://primes.utm.edu/glossary/page.php?sort=FibonacciPrime|titolo=Fibonacci prime |linguaaccesso=en14 gennaio 2011}}.</ref> Si congettura invece che glivi unicisiano solo un numero finito di [[numero primo di Fermat|primi di Fermat]], i numeri primi nella forma 2^{2^''n''} + 1.<ref>{{cita|Hardy sianoe Wright|p. 15|Hardywright}}.</ref> Al momento, gli unici primi di Fermat noti sono in corrispondenza di ''n'' = 0, 1, 2, 3 e 4.

== Formule per i numeri primi ==

{{vedi anche|Formula 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 [[limite (matematica)|limiti]] né a [[serie (matematica)|serie]] né a sommatorie la cui lunghezza dipenda dal dato iniziale) per trovare tutti i numeri primi fino a ''n'', o anche solo l<nowiki>{{'</nowiki>}}''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 di Mills|costante θ]] tale che

:<math>\lfloor \theta^{3^n}\rfloor</math>

è 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]].<ref>{{cita pubblicazione|url=httphttps://www.cs.uwaterloo.ca/journals/JIS/VOL8/Caldwell/caldwell78.pdf|titolo=Determining Mills' Constant and a Note on Honaker's Problem|autore=Chris Caldwell e |autore2=Yuanyou Cheng|rivista=Journal of Integer Sequences|volume=8|anno=2005|accesso=2009.06.2314 gennaio 2011}}</ref>

A seguito della dimostrazione del [[teorema di MatijasevičMatiyasevich]], 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, ede inoltre assumono spesso valori negativi.<ref name=littlebook>{{cita libro|url=http://books.google.it/books?id=zUCK7FT4xgAC&pgprintsec=PA115&lpg=PA115&dq=matijasevic+primes&&ots=c_pvnaCbjW&sig=QVkBsPv3kVZksNBng-rDu08-qOofrontcover&hl=en&eisource=zmBASsv9L5mwsgbd5tnMDw&sa=X&oigbs_navlinks_s#v=book_resultonepage&ctq=result&resnumf=1false|titolo=The little book of big primes|autore=Paulo Ribenboim|anno=1996|ideditore=Springer-Verlag|p=116|accesso=14 ISBNgennaio 2011|ISBN=3-540-97042-8|pagine=116}}</ref>

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 [[Teoria della complessità computazionale|complessità computazionale]].

== Aspetti computazionali ==

Riga 309 ⟶ 307:

{{Vedi anche|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 dimostartorecentemente chedimostrato appartieneappartenere alla [[classe di complessità]] [[P (complessità)|P]].<ref>{{cita web|lingua =en|titolo=PRIMES is in P little FAQ|url=http://www.instantlogic.net/publications/PRIMES%20is%20in%20P%20little%20FAQ.htm|data=2214 settembregennaio 20082011|accesso=94 dicembresettembre 2008}}</ref>

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 <math>\sqrt{N}</math>. Sebbene molto semplice da descrivere e da implementare su un calcolatore, tale metodo è poco usato nella pratica, perché richiede tempi di calcolo che aumentano [[Funzione esponenziale|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 nonsenza determinandodeterminare 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 [[test di Fermat|di Fermat]] e [[test di Wilson|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 [[teorema di Proth|di Proth]], che si applicano solo ai [[numero primo di Mersenne|numeri di Mersenne]] e [[numero di Proth|di Proth]] rispettivamente. Altri, come il [[test di Miller-Rabin]], sono [[probabilità|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 "[[pseudoprimo|pseudoprimi]]". La classe più famosa di pseudoprimi è quella dei [[numero di Carmichael|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'[[Algoritmo ECPP|ECPP]], basato sulle [[curva ellittica|curve ellittiche]];<ref>{{cita web|url=http://mathworld.wolfram.com/EllipticCurvePrimalityProving.html|titolo=Elliptic Curve Primality Proving|autore=Eric W. Weisstein|sito=MathWorld|accesso=3 settembre 2009}}</ref> sebbene la sua [[complessità computazionale]] non sia nota, sperimentalmente si osserva che esso è un [[P (complessità)|algoritmo polinomiale]] nel numero delle cifre di ''n''.<ref>{{cita web|lingua=en |url=http://primes.utm.edu/prove/prove4_2.html |editore=The Prime Pages|accesso=914 dicembregennaio 20082011|titolo=Elliptic curves and ECPP test}}, da {{cita libro|autore= Lenstra Jr. K., |autore2=Lenstra, |autore3=Jr. H. W.|capitolo= Algorithms in number theory. |titolo=Handbook of Theoretical Computer Science Vol A: Algorithms and Complexity|editore= The MIT Press|città= Amsterdam and New York|paginepp= 673-715|anno=1990|idISBN= MR 1 127 1780-444-88071-2}}.</ref> 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 (complessità)|P]].<ref>{{cita web|lingua=en|url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf|autore=Manindra Agrawal, |autore2=Neeraj Kayal, |autore3=Nitin Saxena|titolo=PRIMES is in P|accesso=2314 febbraiogennaio 20092011}}</ref>

=== 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 rispetto a programmi ideati solo per quest'ultimo scopo. Dopo il metodo di divisione per tentativi, i più antichi algoritmi di questo tipo sono il [[metodo di fattorizzazione di Fermat|metodo di Fermat]], che si basa sulle differenze tra il numero da fattorizzare ''N'' e deialcuni quadrati, efficace in particolare quando ''N'' è il prodotto di due numeri primi vicini tra loro, e il [[metodo di fattorizzazione di Eulero|metodo di Eulero]], che si basa invece sulla rappresentazione di ''N'' come [[Teorema di Fermat sulle somme di due quadrati|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 [[frazione continua|frazioni continue]] o le [[curva ellittica|curve ellittiche]], mentre altri, come ad esempio il [[crivello quadratico]], sono basati su miglioramenti del metodo di Fermat. Altri ancora, come il [[Algoritmo rho di Pollard|metodo rho di Pollard]], sono ''probabilistici'', e non offrono la garanzia che, dato un numero non primo, ne trovino i divisori.

AdA oggi il più veloce algoritmo deterministico di impiego generale, ovvero senza necessità di numeri in forma particolare, è il ''[[Crivello dei campi di numeri generale|general number field sieve]]'', che ha complessità esponenziale sul numero di cifre di ''N'';<ref>{{cita web|lingua=en|url=http://mathworld.wolfram.com/NumberFieldSieve.html|autore=Eric W. Weisstein|titolo=Number Field Sieve|accesso=2314 febbraiogennaio 20092011}}</ref> è stato proposto un algoritmo che ha tempo di esecuzione polinomiale nel numero di cifre di ''N'' ([[algoritmo di fattorizzazione di Shor|algoritmo di Shor]]), ma esso richiede di essere eseguito su un [[computer quantistico]], la cui simulazione su un normale calcolatore richiede un tempo esponenziale.<ref>{{cita libro|autore=Samuel J. Lomonaco jr.|titolo=Shor's Quantum Factoring Algorithm, in Quantum Computation - A Grand Mathematical Challenge for the Twenty-First Century and the Millennium|anno=2002|editore=AMS|url=https://www.csee.umbc.edu/~lomonaco/ams/lecturenotes/SamShor.pdf|accesso=14 gennaio 2011|ISBN=0-8218-2084-2}}</ref>

==== Impiego nella crittografia ====

{{vedi anche|RSA (crittografia)}}

Proprio la difficoltà di fattorizzare grandi numeri ha portato allo sviluppo del primo metodo efficace di [[Crittografia asimmetrica|crittografia a chiave pubblica]], l'[[RSA (crittografia)|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 10⁵⁰1024 o 2048 [[Bit (informatica)|bit]]), mentre gli altri due (''e'' ed ''f'') verificanosono lal'uno relazionel'[[Elemento <math>ef\equivinverso|inverso]] 1\moddell'altro \phi[[aritmetica modulare|modulo]] φ(''n'')</math>, (dove <math>\phi</math>φ èindica la [[Funzione φ di Eulero|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 euclidea|divisione]] per ''n''; il [[piccoloTeorema di Eulero (aritmetica modulare)|teorema di FermatEulero]] garantisce che dopo quest'operazione si possa ritornare allo stesso numero di partenza conoscendo sia ''e'' chesia ''f''.

Bisogna notare che èÈ possibile, in teoria, ricavare la chiave privata dalle informazioni pubbliche: attualmente questo richiede la fattorizzazione del numero ''n'', edrendendo essendo questa un'operazione che richiede molto tempo di calcolo,quindi la trasmissione del messaggio si può considerare sicura se i due primi scelti soddisfano alcune condizioni e sono "sufficientemente" grandi. Non è ancora noto se vi siano metodi efficienti per decriptare il messaggio che non prevedano l'attacco diretto alla fattorizzazione di ''n'', ma è stato mostrato che una cattiva scelta della chiave pubblica potrebbe rendere il sistema più vulnerabile ad attacchi di questo tipo.<ref>{{cita web|autore=[[Ronald Rivest|Ron Rivest]] e Burt Kaliski|titolo=RSA Problem|url=https://people.csail.mit.edu/rivest/RivestKaliski-RSAProblem.pdf|data=10 dicembre 2003|accesso=14 gennaio 2011|dataarchivio=17 maggio 2011|urlarchivio=https://web.archive.org/web/20110517084549/http://people.csail.mit.edu/rivest/RivestKaliski-RSAProblem.pdf|urlmorto=sì}}</ref>

Nel [[1991]] la [[RSA LaboratoriesSecurity]] (l'azienda che ha sfruttato commercialmente l'RSA) ha pubblicato una lista di [[semiprimo|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, mamentre per altri il problema è ancora aperto; il concorso si è terminatocomunque concluso nel [[2007]].<ref>{{cita web|lingua=en|url=httphttps://groups.google.com/group/sci.crypt/msg/a20e42af47ec4a12|titolo=Announcement of "RSA Factoring Challenge"|autore=Burt Kaliski|data=18 marzo 1991|accesso=2314 febbraiogennaio 20092011}}</ref><ref>{{en}}[httpcita web|url=https://www.rsa.com/rsalabs/node.asp?id=2094 |titolo=RSA Challenge - FAQ]|accesso=14 gennaio 2011|editore=RSA Laboratories|lingua=en|urlmorto=sì|urlarchivio=https://web.archive.org/web/20100213212458/http://www.rsa.com/rsalabs/node.asp?id=2094|dataarchivio=13 febbraio 2010}}</ref><ref>{{cita web|lingua=en|url=http://mathworld.wolfram.com/RSANumber.html|autore=Eric W. Weisstein|titolo=RSA Number|accesso=2314 febbraiogennaio 20092011}}</ref>

=== Numeri primi grandi ===

{{Vedi anche|Maggior numero primo conosciuto}}

[[File:Largest known prime number by year.svg|thumb|300px|Il numero di cifre decimali del più grande numero primo conosciuto, dal [[1900]] al [[2008]].]]

[[File:Largest known prime number.svg|thumb|upright=1.4|Il numero di cifre (in [[sistema numerico decimale|base 10]]) del più grande numero primo conosciuto, dal 1900 al 2018. La scala sull'asse delle ordinate è logaritmica.]]

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 diquando [[Marin Mersenne]], che affermavacongetturò che <math>M_n=2^n-1</math> sarebbe stato primo (quando ''n''< ≤ 257) solo per ''n'' uguale a 2, 3, 5, 7, 13, 19, 31, 67, 127 e 257.<ref>{{cita|Du Sautoy, op. cit., |p. 78|Sautoy}}.</ref> La verifica della primalità di tali numeri era molto al di làsopra delle possibilità dell'epoca, ede infatti soltanto nel [[XX secolo|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.

''M''₁₂₇ (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 usandovennero untrovati calcolatore(2¹⁴⁸+1)/17 elettronico(di fu44 trovatocifre) ile, primopoco più tardi, 180 · (2¹²⁷- − 1)² + 1, (di 79 cifre), quest'ultimo tramite un calcolatore elettronico. Da allora tutti i successivi primi più grandi sono stati scoperti con l'aiuto del computer: dal [[1952]] (quando lo [[SWAC]] dimostrò che ''M''₅₂₁ è primo) al [[1996]] essi sono stati trovati da [[supercomputer]], e furono tutti [[numero primo di Mersenne|primi di Mersenne]] (trovati usando il [[test di Lucas-Lehmer]], un algoritmo specifico per questi numeri) adcon l'eccezione di 391581 · 2²¹⁶¹⁹³- − 1, che detenne il record tra il [[1989]] e il [[1992]].<ref name=largestbyyear>{{cita web|lingua=en|url=http://primes.utm.edu/notes/by_year.html|autore=Chris Caldwell|titolo=The Largest Known Prime by Year: A Brief History|sito=The Prime Pages|accesso=2314 febbraiogennaio 20092011}}</ref><ref>{{cita|Du Sautoy, op. cit., |capitolo 9|Sautoy}}.</ref>

In seguito, i dodiciquattordici nuovi numeri primi più grandi sono stati scoperti attraverso il [[GIMPS]], un progetto di [[calcolo distribuito]] basato anch'esso sul test di Lucas-Lehmer. IlA oggi (dicembre 2018) il più grande numero primo confermato, scoperto nell'[[agosto]]nel dicembre del [[2008]]2018, è 2^{43.112.609{{formatnum:82589933}}}- − 1, uncomposto numeroda dioltre quasi tredici24 milioni di cifre decimali.<ref>{{cita web|lingua=en|url=http://mersenneprimes.orgutm.edu/m45and46top20/page.htmphp?id=3|titolo=TitanicThe Top Twenty: Largest Known Primes|accesso=21 Raceddicembre to2018}}</ref><ref>{{cita Winweb|url=https://www.mersenne.org/primes/?press=M82589933|titolo=GIMPS $100Discovers Largest Known Prime Number: 2^{82,000589,933}-1|sito=[[GIMPS|mersenne.org]]|data=21 Researchdicembre Award2018|accesso=2321 febbraiodicembre 20092018|lingua=en}}</ref> 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 perai laprimi primache scopertariusciranno dia trovare numeri primi di oltre un certo numero di cifre. I primi due di questi premi, di 50.000{{formatnum:50000}} e 100.000{{formatnum:100000}} [[dollaro statunitense|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{{formatnum:250000}} dollari, per l'arrivo al miliardo di cifre.<ref>{{cita web|lingua=en|url=httphttps://www.eff.org/awards/coop|titolo=EFF Cooperative Computing Awards|accesso=23 febbraio 2009}}</ref><ref>{{cita web|lingua=en|url=http://www.tgdaily.com/content/view/39527/113|titolo=Scoperto un primo di oltre 13 milioni di cifre|accesso=2314 febbraiogennaio 20092011}}</ref>

== Generalizzazioni ==

[[File:Gaussian primes.pngsvg|thumb|250px|Rappresentazione dei primi di Gauss di norma minore o uguale a 500. I primi di Gauss sono, per definizione, gli elementi tra gli [[intero gaussianodi Gauss|interi di Gauss]] che sono primi.]]

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

Riga 357 ⟶ 356:

=== 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 è [[Elemento inverso|invertibile]] chee non può essere scritto come il prodotto di due elementi anch'essi non invertibili;<ref group="N">definizione corrispondente a quella data sopra.</ref>

* un elemento è ''primo'' se non è invertibile e ogni volta che divide il prodotto <math>''ab</math>'', allora divide <math>''a</math>'' oppure <math>''b</math>''.<ref group="N">Ad esempio 5 divide <math>45 = 15 \times× 3</math> e divide 15, mentre 4, che non è primo, divide <math>84 = 14 \times× 6</math>, ma non divide né 14 né 6.</ref>

NellUn elemento primo è sempre irriducibile, ma non viceversa: tuttavia nell'anello degli [[numero intero|interi]] le due definizioni sono equivalenti (come garantito dal [[lemma di Euclide]]), e più in generale sono equivalenti in tutti gli [[anellodominio a fattorizzazione unica|anelli a fattorizzazione unica]].

Inoltre, dato un [[anello (algebra)|anello]] ''A'', un [[ideale (matematica)|ideale]] ''I'' di ''A'' è detto "primo" se per ogni coppia ''a'',''b'' di elementi di A tali che <math>ab\in''a''·''b'' ∈ ''I</math>'' almeno uno tra ''a'' e ''b'' appartiene a ''I''.

Questa definizione è molto vicina a quella degli ordinari numeri primi, tanto che nell'anello <math>\mathbb{Z}</math> gli interi gli[[Ideale primo|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 algebrica dei numeri algebrica]]. Un'importante analogia tra numeri primi e ideali primi è dato dal fatto che nei [[anellodominio di Dedekind|domini di Dedekind]] per gli ideali vale l'analogo del [[teorema fondamentale dell'aritmetica]].<ref group="N">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.</ref>

=== Teoria dei gruppi ===

Nella [[teoria dei gruppi]], iun [[gruppiruolo sporadici]]simile sonoa considerati l'equivalentequello dei numeri primi: siè dimostrarivestito che ogni gruppo semplice finito può esseredai [[gruppo ciclicosemplice|ciclicogruppi semplici]],. alternato,Si unopuò deidimostrare 16infatti tipiche diogni [[gruppo difinito Lie|gruppi''G'' sempliciammette finitiuna [[serie di Liecomposizione]], ocioè unouna deiserie 26del [[gruppi sporadici]].tipo

:<math>1 = H_0\triangleleft H_1\triangleleft \cdots \triangleleft H_m = G,</math>

ove ogni ''H''_''i'' è un [[sottogruppo normale]] di ''H''_''i''+1 tale che il gruppo ''H''_''i''+1 / ''H''_''i'' (detto gruppo fattore della serie) sia un gruppo semplice. Il [[teorema di Jordan-Hölder]] assicura che tutte le serie di composizione per ''G'' hanno la stessa lunghezza ''m'' e gli stessi fattori di composizione, a meno di [[permutazione|permutazioni]] e [[Isomorfismo tra gruppi|isomorfismi]]. È tuttavia da notare che gruppi diversi possono avere la stessa serie di composizione: ad esempio il [[gruppo ciclico]] <math>\mathbb{Z}_{2p}</math> e il [[gruppo diedrale]] ''D_p'', per ogni primo ''p'', hanno entrambi la serie di composizione

:<math>1\triangleleft\mathbb{Z}_p\triangleleft G,</math>

corrispondente ai fattori <math>\mathbb{Z}_2</math> e <math>\mathbb{Z}_p</math>.

=== Teoria dei nodi ===

{|class="wikitable" style="margin-bottom: 1em; margin-left: 1em;" align="right"

|[[File:TrefoilKnot- 01.pngsvg|Trefoil|50 px]] || [[File:PrimeKnot-4-1.png|Figure-8 knot]] || [[File:Knot-cinquefoil-sm.png|Cinquefoil]] || [[File:PrimeKnot-5-2.png]]

|-

| colspan="4" align="center" |Alcuni nodi primi

|}

In [[teoria dei nodi]], un [[nodo primo]] è un [[nodo (matematica)|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.<ref>[{{cita web|autore=Eric W. Weisstein|url=http://mathworld.wolfram.com/PrimeKnot.html|titolo=Prime Su Mathworldknot|sito=[[MathWorld].]|accesso=14 gennaio 2011}}</ref> 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 ==

[[File:530937661 c29fba0c57 b.jpg|thumb| Una ''[[Magicicada]]'' con periodo di 17 anni]]

In natura compaiono molti numeri, ed è quindi inevitabile che alcuni di essi siano primi. Sono tuttavia relativamente pochi gli esempi di numeri la cui presenza in natura si spieghi con la loro primalità.

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,Per la maggior parte, dellele [[Asteroidea|stelle marine]] hanno 5 braccia, e 5 è un numero primo; tuttavia non è statonota trovatoalcuna alcunconnessione motivo evidente per supporre chetra questo numero di braccia siae in qualche modo legato allala primalità di 5.<ref group="N">Alcune stelle marine hanno un numerodiverso differentenumero di braccia: ad esempio, l<nowiki>'</nowiki>''[[Echinaster luzonicus]]'', ad esempio, ha normalmente sei braccia, mentre la ''[[Luidia senegalensis]]'' ha nove braccia e la ''[[Solaster endeca]]'' può avere anche 20 braccia.</ref> Il motivo perdella cuisimmetria a 5 braccia che caratterizza la maggior parte delle stelle marine, così comee molti altri [[Echinodermata|echinodermi]], hanno una simmetria a 5 braccia rimane un mistero.

In [[entomologia]] si trova uno dei casi in cui si suppone che un numero comparecompaia proprio perchéin èquanto primo. ÈSi statoè infatti notato che alcune specie di [[cicala (insetto)Cicadidae|cicale]] del genere ''[[Magicicada]]'',<ref>{{en}}Goles, E., Schulz, O. e M. Markus (2001). "Prime number selection of cycles in a predator-prey model", Complexity 6(4): 33-38.</ref> che trascorrono la maggior parte delle loro vite come [[larva|larve]], emergono come pupe solo a intervalli di 13 o 17 anni, dopo idi qualiche si riproducono e infine muoiono dopo poche settimane. Si pensa che il motivo per cui l'intervallo di tempo siaè un numero primo di anni èsia la difficoltà per un predatore di evolversi specializzandosi comenella predatoripredazione delle ''Magicicada'':<ref>{{en}}{{cite journal | author = Paulo R. A. Campos, Viviane M. de Oliveira, Ronaldo Giro e Douglas S. Galvão. | url = http://link.aps.org/abstract/PRL/v93/e098107 | title = Emergence of Prime Numbers as the Result of Evolutionary Strategy | journal = [[Physical Review Letters|Phys. Rev. Lett.]] | volume = 93 | doi = 10.1103/PhysRevLett.93.098107 | year = 2004 | accessdate = 23 febbraio 2009 }}</ref> se infatti questi insetti apparissero dopo un numero non primo di anni, allora tutti i predatori il cui ciclo vitale èfosse un divisore di quel numero sarebberoavrebbero sicuriuna elevata probabilità di trovare le ''Magicicada''. SeSebbene iesile, periodiquesto divantaggio questievolutivo insettisembra fosseroessere invecestato disufficiente 14a oselezionare 15cicale anniil sicui stimaperiodo che dopo due secoli ci sarebbe una popolazioneè di predatori13 delo 2%17 più altaanni.<ref>{{en}}{{cite webcita pubblicazione|workautore=[[ThePaulo Economist]]|R. url=http://economistA.com/PrinterFriendly Campos, Viviane M.cfm?Story_ID=2647052 de Oliveira, Ronaldo Giro e Douglas S. Galvão|titletitolo=InvasionEmergence of Prime Numbers as the BroodResult of Evolutionary Strategy|dateurl=https://link.aps.org/abstract/PRL/v93/e098107|rivista=[[6Physical maggio]]Review [[2004Letters|Phys. Rev. Lett.]]|accessdatevolume=2393|anno=2004|doi=10.1103/PhysRevLett.93.098107|accesso=14 febbraio 2009gennaio 2011}}</ref><ref>{{en}}{{cita Sebbenepubblicazione|E. esileGoles, questoO. vantaggioSchulz, evolutivoM. sembraMarkus|titolo=Prime esserenumber statoselection sufficienteof acycles selezionarein cicalea il cui periodopredator-prey è 13 o 17 anni.model|rivista=Complexity|volume=6|numero=4|pp=33-38}}</ref>

== 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 <ref name= Du_Sautoy > {{cita libro|cognome= Du Sautoy|nome= Marcus|wkautore= Marcus du Sautoy|coautori= |curatore= Michael Emmer|altri= |titolocapitolo= Un ''divertissement in prima serata'', in ''|titolo=Matematica e cultura 2006''|url= http://books.google.it/books?id=GUW8v0u56dYC&printsec=frontcover&source=gbs_summary_r&cad=0|formato= |datadiaccessoaccesso= 274 aprilesettembre 2008|anno= 2006|editore= Springer|cittàpp= |lingua=201-207 |id= ISBN 9788847004641|pagine= 201978-207 88-470-0464-1}} </ref> 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".<ref>{{cita libro|titolo=The Messiaen companion|autore=Peter Hill|editore=Amadeus Press|anno=1994|ISBN=ISBN 0-931340-95-0}}.</ref> Anche nel movimento di apertura di un'altra composizione, ''[[Quatuor pour la fin du temps]]'', Messiaen utilizzò i numeri primi. Con l'obbiettivoobiettivo di dare l'idea dell'eternità, accostò infatti un tema di 17 note ada 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.<ref name= Du_Sautoy />

I numeri primi svolgono un ruolo anche in alcuni libri. Ad esempio, nel romanzo di fantascienza ''[[Contact (romanzo)|Contact]]'' di [[Carl Sagan]] (così come nella sua [[Contact (film)|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 [[autismo|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 (scrittore)|Paolo Giordano]] ''[[La solitudine dei numeri primi]]'', vincitore del [[premio Strega]] nel 2008. Il romanzo ''Lo zio Petros e la congettura di Goldbach'' di [[Apostolos Doxiadis]] (pubblicato in italiano nel 2001) è stato trasposto per le scene da [[Angelo Savelli]].<ref>Angelo Savelli, ''[http://www.springerlink.com/content/978-88-470-0346-0/#section=593676&page=1 Zio Petros tra scienza, letteratura e teatro]'', in Mirella Manaresi (a cura di), ''[http://books.google.it/books?id=o-TlWNLC710C Matematica e cultura in Europa]'', Milano, Springer, 2005, pp. 305-312. ISBN 88-470-0346-6; ISBN 978-88-470-0346-0.</ref>

Molti film riflettono la fascinazione popolare verso i misteri dei numeri primi e della crittografia, come ad esempio ''[[Cube - Il cubo]]'',<ref>Alberto Perelli, in Mirella Manaresi, ''op. cit.'', [http://www.springerlink.com/content/978-88-470-0346-0/#section=593663&page=1 pp. 230-244].</ref> ''[[I signori della truffa]]'', ''[[L'amore ha due facce]]''<ref>Michele eEmmer, ''[[ibidem]]'', [http://www.springerlink.com/content/978-88-470-0346-0/#section=593665&page=1 pp. 245-253].</ref>, ''[[A beautifulBeautiful Mind]]''<ref>Marco Li Calzi, ''[[ibidem]]'', [http://www.springerlink.com/content/978-88-470-0346-0/#section=593657&page=1 pp. 187-206].</ref> e ''[[La solitudine dei numeri primi (film)|La solitudine dei numeri mindprimi]]''.

== Note ==

;Annotazioni

{{references|2}}

<references group="N"/>

;Fonti

<references/>

== Bibliografia ==

* {{en}} {{Cita libro| Tomautore M.= | Apostol |wkautore=[[Tom M. Apostol]]| titolo=Introduction to Analytic Number Theory| anno=1976 | Apringereditore=Springer-Verlag | città=New York | ided=2|lingua=en|cid=Apostol|ISBN =0-387-90163-9|ed=2}}

* {{Cita libro| Carlautore B.= | BoyerMichael Artin| titolo=Algebra|wkautore anno=1997 Carl Benjamin Boyer|Storiaeditore= dellaBollati matematicaBoringhieri|1990 città=Torino| Mondadori cid=Artin| Milano | idISBN=ISBN 978-88-04339-334315586-69}}

* {{Cita libro| John H. | Conway |wkautoreautore=John H. Conway | coautori=[[RichardCarl KB. GuyBoyer]] |titolo=[[Storia Ildella libromatematica dei numeri(Boyer)|Storia 1999della matematica]]|anno=1990 Hoepli|editore=Mondadori |città= Milano | idcid=Boyer|ISBN =978-88-20304-251933431-56}}

* {{Cita libro|autore= Harold[[John Conway|John DavenportH. |Conway]] wkautore=Harolde Davenport[[Richard |K. AritmeticaGuy]] superiore| 1994titolo=Il libro dei numeri| Zanichellianno=1999 | Bolognaeditore=Hoepli | idcittà=ISBNMilano |cid=Conwayguy|ISBN=88-08203-091542519-65}}

* {{Cita libro| Keith |autore=[[Harold DevlinDavenport]] | Dove va la matematica|titolo=Aritmetica superiore|wkautore anno= Keith Devlin| 1994 | Bollati Boringhierieditore=Zanichelli | Torinocittà=Bologna | idcid=Davenport|ISBN =88-33908-118209154-96}}

* {{Cita libro| Marcusautore= |[[Keith du SautoyDevlin]] | wkautoretitolo=MarcusDove duva Sautoy|la [[L'enigma dei numerimatematica primi]]| 2004anno=1994 | Rizzolieditore=Bollati Boringhieri | Milanocittà=Torino | idcid=ISBNDevlin| ISBN=88-17339-008431182-59}}

* {{en}} {{Cita libro| Albertautore= Edward[[Marcus | Inghamdu Sautoy]]| wkautoretitolo=Albert[[L'enigma Edwarddei Ingham|The Distribution of Primenumeri Numbersprimi]]| 1932anno=2004 | Cambridge Mathematical Libraryeditore=Rizzoli | New Yorkcittà=Milano |cid=Sautoy| id=ISBN 0=88-52117-3978900843-85}}

* [[Euclide]], ''[[Elementi (Euclide)|Elementi]]''

* {{en}} {{Cita libro| Leo | Moser | An Introduction to the Theory of Numbers| 2004 | The Trillia Group | West Lafayette (Indiana, USA) | id=ISBN 978-1-931705-01-1 | url=http://www.trillia.com/moser-number.html |formato=PDF |datadiaccesso = 2009-01-29}}

* {{Cita libro| autore= Richard K. Guy|titolo=Unsolved problems in number theory| url= https://archive.org/details/unsolvedproblems0003guyr| anno=2004 | editore= Springer-Verlag | città=New York|lingua=en| ed=3|cid=Guy|ISBN=0-387-20860-7}}

* {{Cita libro| Giulia Maria | Piacentini Cattaneo | Algebra - un approccio algoritmico| 1996 | Decibel-Zanichelli | Padova | id=ISBN 978-88-08-16270-0}}

* {{cita libro | autore= [[Godfrey Harold Hardy]] e [[Edward M. Wright]]|editore = Oxford University Press|titolo = An Introduction to the Theory of Numbers |ed=6 |città=Oxford | anno = 2008 |lingua=en|cid=Hardywright|ISBN=978-0-19-921986-5}}

* {{Cita libro| autore= Albert Edward Ingham|wkautore=Albert Ingham|titolo=The Distribution of Prime Numbers| anno=1932 | editore=Cambridge University Press| città=Cambridge|lingua=en|cid=Ingham|ISBN=0-521-39789-8}}

* {{Cita libro| autore=Leo Moser | titolo=An Introduction to the Theory of Numbers| 2004 | editore=The Trillia Group | città=West Lafayette (Indiana, USA) | url=http://www.trillia.com/moser-number.html |lingua=en|accesso= 1º settembre 2009|cid=Moser|ISBN=978-1-931705-01-1}}

* {{Cita libro| autore=Giulia Maria Piacentini Cattaneo | titolo=Algebra - un approccio algoritmico| anno=1996 | editore=Decibel-Zanichelli | città=Padova | ISBN=978-88-08-16270-0}}

* {{Cita libro| autore=[[Simon Singh]]| titolo=[[Codici & segreti]]| anno=1999 | editore=Rizzoli|città=Milano| ISBN=88-17-86213-4}}

* {{Cita libro| autore= [[Ian Stewart (matematico)|Ian Stewart]] e David Tall|titolo=Algebraic number theory and Fermat's last theorem| url= https://archive.org/details/algebraicnumbert0000stew_o8a3| anno=2002 | editore= A K Peters| città=Natick, Massachusetts |lingua=en|ed=3|cid=Stewartall|ISBN=1-56881-119-5}}

* {{Cita libro| autore= [[Terence Tao]] e Van Vu|titolo= Additive combinatorics| anno=2006 | editore= Cambridge University Press | città=Cambridge|lingua=en|cid=Taovu|ISBN=978-0-521-85386-6}}

* {{Cita libro| autore=Song Y. Yan|titolo=Primality testing and integer factorization in public-key cryptography| url=https://archive.org/details/primalitytesting0000yans| anno=2004 | editore= Kluwer Academic Publishers| città=Boston|lingua=en|cid=Yan|ISBN=1-4020-7649-5}}

== Voci correlate ==

{{MultiColColonne}}

;Principali teoremi e congetture sui numeri primi

* [[Congettura dei numeri primi gemelli]]

* [[Congettura di Legendre]]

* [[Congettura di Goldbach]]

* [[Congettura di Opperman]]

* [[Ipotesi di Riemann]]

* [[Reciprocità quadratica|Legge di reciprocità quadratica]]

* [[Numero primo di Mersenne]]

* [[Piccolo teorema di Fermat]]

* [[Postulato di Bertrand]]

* [[Teorema di Fermat sulle somme di due quadrati|Teorema di Fermat sui primi rappresentabili come somma di due quadrati]]

* [[Teorema dei numeri primi]]

* [[Teorema dell'infinità dei numeri primi]]

Riga 427 ⟶ 445:

* [[Teorema di Wilson]]

* [[Test di Fermat]]

* [[Test di Lucas - Lehmer]]

* [[Test di Miller - Rabin]]

{{ColBreakColonne spezza}}

;Numeri primi

* [[Lista di numeri primi]]

* [[Numero omirp]]

* [[Numeri primi cugini]]

* [[Numero primo di Eisenstein]]

* [[Numero primo di FermatBelfagor]]

* [[Numero di Fermat]]

* [[Numero primo di Mersenne]]

* [[Numero primo di Sophie Germain]]

* [[Numero primo troncabile]]

* [[Numeri primi gemelli]]

* [[NumeriNumero primiprimo illegaliillegale]]

* [[Numeri primi sexy]]

* [[Primo palindromo]]

* [[Primo circolare]]

* [[Primo cubano]]

* [[PrimoRepunit#Primi repunit]]

;Altre

* [[Costante di Copeland-Erdős]]

* [[Algoritmi per la generazione dei numeri primi]]

* [[Costante di Copeland-Erdos]]

* [[Criteri di divisibilità]]

* [[Crivello di Eratostene]]

Riga 451 ⟶ 472:

* [[Intero gaussiano]]

* [[Ipotesi di Riemann]]

* [[Maggior numero primo conosciuto]]

* [[Spirale di Ulam]]

* [[Numero pratico]]

{{EndMultiCol}}

{{Colonne fine}}

== Altri progetti ==

{{interprogetto|q|q_preposizione=sui|etichettawikt=numerinumero primiprimo|commonswikt_etichetta=Category:Primenumero numbersprimo}}

{{interprogetto/notizia|Scoperti i due nuovi numeri primi più grandi a distanza di pochi giorni|data=18 settembre 2008}}

{{Interprogetto/notizia|Intervista a Marcus du Sautoy|data=4 ottobre 2007}}

== Collegamenti esterni ==

* {{Collegamenti esterni}}

* {{mathworld|PrimeNumber|Articolo sui numeri primi}}

* {{cita web|autore=Chris Caldwell|url=http://www.utm.edu/research/primes/|titolo=The Prime Pages|accesso=11 settembre 2009|lingua=en|dataarchivio=1 agosto 2003|urlarchivio=https://web.archive.org/web/20030801082511/http://www.utm.edu/research/primes/|urlmorto=sì}}

* {{it}} [http://matematica.uni-bocconi.it/LangZac/primi.htm Cosa sono i numeri primi (spiega perché 1 non viene considerato primo)]

* {{it}}cita web|titolo=Il mistero dei numeri primi e la sicurezza informatica|autore=Laura [Listanti|formato=PDF|url=http://ulisse.sissa.it/biblioteca/saggio/2006/Ubib060301s001/at_download/file/Ubib060301s001.pdf|accesso=11 Ilsettembre mistero2009|urlmorto=sì|urlarchivio=https://web.archive.org/web/20110722053118/http://ulisse.sissa.it/biblioteca/saggio/2006/Ubib060301s001/at_download/file/Ubib060301s001.pdf|dataarchivio=22 deiluglio numeri primi e la sicurezza informatica]2011}}

* {{en}}cita [httpweb|titolo=Fast Online primality test with factorization|url=https://www.alpertron.com.ar/ECM.HTM|accesso=28 Testaprile interattivo2014|lingua=en}} dijava primalitàaplet eche fattorizzazioneimplementa diil grandi[[Algoritmo numeri col metodoECPP|Metodo delle curve ellittiche]], capace di testare la primalità di numeri con migliaia di cifre.

* {{cita web|autore=Paolo Ardoino|titolo=Random prime numbers using OpenSSL bignum|url=http://ardoino.com/7-maths-openssl-primes-random/|accesso=11 settembre 2009|lingua=en|urlmorto=sì|urlarchivio=https://web.archive.org/web/20091220193023/http://ardoino.com/7-maths-openssl-primes-random/|dataarchivio=20 dicembre 2009}}

* {{en}} [http://www.utm.edu/research/primes/ The Prime Pages]

* {{cita web|autore=Mark Chamness|titolo=Prime number generator|url=http://alumnus.caltech.edu/~chamness/prime.html|accesso=11 settembre 2009|lingua=en|urlarchivio=https://web.archive.org/web/20090904004013/http://alumnus.caltech.edu/~chamness/prime.html|dataarchivio=4 settembre 2009|urlmorto=sì}}

* {{en}} [http://www.claymath.org/millennium/Riemann_Hypothesis/ Istituto Clay di matematica - premio per l'ipotesi di Riemann]

* {{en}} [http://ardoino.com/7-maths-openssl-primes-random/ Generatore di numeri primi random di grandi dimensioni (programma in C basato sul OpenSSL)]

* {{en}} [http://alumnus.caltech.edu/~chamness/prime.html Generatore di numeri primi online.]

{{Teoria dei numeri}}

{{algebra}}

{{Controllo di autorità}}

{{Portale|matematica}}

{{vetrina|21|settembre|2009|Wikipedia:Vetrina/Segnalazioni/Numero_primo|arg=matematica}}

[[Categoria:Numeri primi| ]]

[[Categoria:Matematica di base]]

[[Categoria:Successioni di interi]]

{{Link AdQ|ru}}

{{Link AdQ|lmo}}

[[af:Priemgetal]]

[[an:Numero primero]]

[[ang:Frumtæl]]

[[ar:عدد أولي]]

[[arz:عدد أولي]]

[[az:Sadə ədəd]]

[[bat-smg:Pėrmėnis skaitlios]]

[[be-x-old:Просты лік]]

[[bg:Просто число]]

[[bn:মৌলিক সংখ্যা]]

[[br:Niveroù kentael]]

[[bs:Prost broj]]

[[ca:Nombre primer]]

[[cs:Prvočíslo]]

[[cy:Rhif cysefin]]

[[da:Primtal]]

[[de:Primzahl]]

[[el:Πρώτος αριθμός]]

[[en:Prime number]]

[[eo:Primo]]

[[es:Número primo]]

[[et:Algarv]]

[[eu:Zenbaki lehen]]

[[fa:عدد اول]]

[[fi:Alkuluku]]

[[fr:Nombre premier]]

[[ga:Uimhir phríomha]]

[[gl:Número primo]]

[[haw:Helu kumu]]

[[he:מספר ראשוני]]

[[hi:अभाज्य संख्या]]

[[hr:Prost broj]]

[[hsb:Primowa ličba]]

[[ht:Nonm premye]]

[[hu:Prímszámok]]

[[id:Bilangan prima]]

[[is:Frumtala (stærðfræði)]]

[[ja:素数]]

[[ka:მარტივი რიცხვი]]

[[ko:소수 (수론)]]

[[la:Numerus primus]]

[[lb:Primzuel]]

[[lmo:Nümar primm]]

[[lt:Pirminis skaičius]]

[[lv:Pirmskaitlis]]

[[ml:അഭാജ്യസംഖ്യ]]

[[mn:Энгийн тоо]]

[[ms:Nombor perdana]]

[[nds:Primtall]]

[[nl:Priemgetal]]

[[nn:Primtal]]

[[no:Primtall]]

[[pl:Liczby pierwsze]]

[[pms:Nùmer prim]]

[[pt:Número primo]]

[[ro:Număr prim]]

[[ru:Простое число]]

[[scn:Nùmmuru primu]]

[[si:ප්‍රථමික සංඛ්‍යා]]

[[simple:Prime number]]

[[sk:Prvočíslo]]

[[sl:Praštevilo]]

[[sq:Numri i thjeshtë]]

[[sr:Прост број]]

[[sv:Primtal]]

[[sw:Namba tasa]]

[[szl:Pjyrszo nůmera]]

[[ta:பகா எண்]]

[[th:จำนวนเฉพาะ]]

[[tr:Asal sayılar]]

[[uk:Просте число]]

[[ur:اولی عدد]]

[[uz:Tub son]]

[[vi:Số nguyên tố]]

[[vls:Priemgetal]]

[[war:Primo nga ihap]]

[[yi:פרימצאל]]

[[yo:Nọ́mbà àkọ́kọ́]]

[[zh:素数]]

[[zh-min-nan:Sò͘-sò͘]]

[[zh-yue:質數]]