Teorema dell'infinità dei numeri primi

Il teorema dell'infinità dei numeri primi afferma che, per quanto grande si scelga un numero naturale n, esiste sempre un numero primo maggiore di n.

È stato dimostrato per la prima volta da Euclide nei suoi Elementi (libro IX, proposizione 20), ma ne sono state trovate circa altre cinquanta dimostrazioni, che usano una gran varietà di tecniche diverse: ad esempio Eulero lo ricavò dalla divergenza della serie armonica e dalla possibilità di scrivere ogni numero come prodotto di numeri primi; Christian Goldbach usò i numeri di Fermat, mentre Harry Furstenberg ideò una dimostrazione che sfrutta i metodi della topologia.^[1]

Alcune di queste dimostrazioni (quella di Euclide, quella di Goldbach e un'altra che usa i numeri di Mersenne) si basano su una strategia simile, ovvero dimostrare che esiste una successione infinita di numeri che sono a due a due coprimi, da cui segue necessariamente l'infinità dei numeri primi.

Dimostrazioni

Dimostrazione di Euclide

La dimostrazione, molto semplice in termini moderni, è esposta negli Elementi di Euclide e può a buon diritto essere considerata la prima dimostrazione di un teorema di teoria dei numeri.

La dimostrazione avviene per assurdo, con il seguente ragionamento:

Si supponga che i numeri primi non siano infiniti ma solo ${\textstyle P=\{2,3,\dots ,p_{n}\}}$; ${\displaystyle p_{n}}$ sarebbe allora il più grande dei numeri primi. Sia ${\textstyle a\in \mathbb {N} }$ il prodotto degli n numeri primi, ${\displaystyle a+1}$ non è divisibile per 2, perché lo è ${\textstyle a}$ e quindi ha resto 1. Non è divisibile per 3, per lo stesso motivo. In generale, detto ${\displaystyle p_{i}}$ l'i-esimo numero primo, la divisione ${\textstyle {\frac {a+1}{p_{i}}}}$ ha sempre resto 1: assumendo ${\textstyle (a+1)}$ come dividendo, ${\displaystyle p_{i}}$ come divisore, ${\textstyle q\in \mathbb {N} }$ come quoziente della divisione, è sufficiente dimostrare che ${\textstyle (a+1)-(q\cdot p_{i})=1}$, cioè che ${\displaystyle a=(q\cdot p_{i})}$ assunto come ipotesi.

A questo punto, per il teorema fondamentale dell'aritmetica, sono possibili due casi:

1. ${\displaystyle a+1}$ è primo, e ovviamente essendo maggiore di ${\displaystyle p_{n}}$ quest'ultimo non è il più grande dei numeri primi;
2. ${\displaystyle a+1}$, non essendo primo, è il prodotto di numeri primi che non possono figurare tra gli ${\displaystyle n}$ ipotizzati (in quanto, come abbiamo appena mostrato, nessun ${\displaystyle p_{i}}$ divide ${\textstyle (a+1)}$) e che devono quindi essere maggiori di ${\displaystyle p_{n}}$; anche in questo caso segue che ${\displaystyle p_{n}}$ non è il più grande dei numeri primi.

In entrambi i casi si perviene alla conclusione che non può non esistere un numero primo più grande di ${\displaystyle p_{n}}$, dunque i numeri primi sono infiniti.

In realtà solo pochi dei numeri ${\displaystyle a+1}$ (detti numeri di Euclide) così trovati sono primi, perché il divario tra ${\displaystyle p_{n}}$ e ${\displaystyle a}$ cresce circa come il fattoriale, e quindi c'è sempre più possibilità che ${\displaystyle a+1}$ abbia un divisore tra ${\displaystyle p_{n}}$ e ${\displaystyle {\sqrt {a+1}}}$.

Una conseguenza immediata di questa dimostrazione è la seguente disuguaglianza:

${\displaystyle p_{n+1}<p_{1}p_{2}\cdots p_{n}}$

La disuguaglianza di Bonse e le sue generalizzazioni forniscono risultati più forti.

Corollario

Lo stesso argomento in dettaglio: Primo fattoriale.

Un interessante corollario, che è evidente rigirando la dimostrazione, è che si può sempre costruire un intervallo, lungo a piacere, di numeri consecutivi che non siano numeri primi. Infatti se vogliamo avere un intervallo di 99 numeri consecutivi senza primi, è possibile costruirlo prendendo, ad esempio, il fattoriale di 100, ossia ${\textstyle 100!}$ ≈ 9,33262154×10¹⁵⁷. Questo numero, enorme, è divisibile per tutti i numeri tra ${\displaystyle 2}$ e ${\displaystyle 100}$, per costruzione. Se poniamo che ${\displaystyle k}$ sia uno di questi numeri tra 2 e 100, ${\textstyle 100!}$ e ${\displaystyle 100!+k}$ sono entrambi divisibili per ${\displaystyle k}$. Abbiamo quindi 99 numeri consecutivi senza primi, da ${\displaystyle 100!+2}$ a ${\displaystyle 100!+100}$. Si noti che, data la lunghezza dell'intervallo, gli estremi dell'intervallo costruito in questo modo non sono i minimi possibili.

Dimostrazione di Eulero

La dimostrazione di Eulero parte dal fatto che la serie armonica:

${\displaystyle S=1+{\frac {1}{2}}+{\frac {1}{3}}+\dots +{\frac {1}{n}}+\dots }$

è divergente.

Eulero osserva che la serie armonica può vedersi come il prodotto di queste serie geometriche, una per ogni numero primo:

${\displaystyle S_{2}=1+{\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+\dots +{\frac {1}{2^{n}}}+\dots =2}$

${\displaystyle S_{3}=1+{\frac {1}{3}}+{\frac {1}{9}}+{\frac {1}{27}}+\dots +{\frac {1}{3^{n}}}+\dots ={\frac {3}{2}}}$

${\displaystyle S_{5}=1+{\frac {1}{5}}+{\frac {1}{25}}+{\frac {1}{125}}+\dots +{\frac {1}{5^{n}}}+\dots ={\frac {5}{4}}}$

...

Le serie si calcolano facilmente ricordando che ${\displaystyle S_{n}={\frac {1}{1-{\frac {1}{n}}}}}$ (vedi serie geometrica).

Infatti la serie armonica è la somma dei reciproci di tutti i numeri naturali e ogni numero naturale può rappresentarsi come il prodotto dei suoi fattori primi. Ci si convince allora facilmente che ogni elemento della serie armonica corrisponde a un possibile prodotto di elementi presi uno ad uno dalle serie suddette. Per esempio per l'elemento ${\displaystyle 1/15}$:

${\displaystyle {\frac {1}{15}}=1\times {\frac {1}{3}}\times {\frac {1}{5}}\times 1\times 1\times \dots }$

D'altra parte le serie ${\displaystyle S_{2},S_{3},S_{5},S_{7},\ldots }$ sono tutte finite. Ma allora se i numeri primi fossero finiti, il loro prodotto sarebbe anch'esso finito, mentre sappiamo che la serie armonica diverge.

Ne segue che i numeri primi devono essere infiniti.

Dimostrazione topologica

Per ogni coppia di interi ${\displaystyle a}$ e ${\displaystyle b,}$ con ${\displaystyle a>0,}$ si ponga ${\displaystyle a\mathbb {Z} +b:=\{an+b:n\in \mathbb {Z} \}}$. La famiglia ${\displaystyle \{a\mathbb {Z} +b:a,b\in \mathbb {Z} ,a>0\}}$ è una base di una topologia di ${\displaystyle \mathbb {Z} }$, detta topologia degli interi equispaziati: la prova dell'infinitudine dei numeri primi si cela dietro le sue proprietà topologiche. Gli aperti di tale topologia godono di tre proprietà:

1. ogni aperto ${\displaystyle a\mathbb {Z} +b}$ è chiuso;
2. ogni aperto non vuoto ha infiniti elementi;
3. ${\displaystyle \mathbb {Z} \backslash \{-1,1\}=\bigcup _{p\in \mathbb {P} }p\mathbb {Z} }$, ove ${\displaystyle \mathbb {P} }$ è l'insieme dei numeri primi positivi.

La 2 è immediata e la 3 discende dal teorema fondamentale dell'aritmetica. Per quanto riguarda la 1 è sufficiente notare che

${\displaystyle a\mathbb {Z} +b=\mathbb {Z} \backslash \bigcup _{m=b+1}^{a+b-1}(a\mathbb {Z} +m).}$

Se ${\displaystyle \mathbb {P} }$ fosse finito, in virtù della 3 e della 1, avremmo che ${\displaystyle \{-1,1\}}$ è aperto, ma ciò è in contraddizione con la 2.

Note

Bibliografia

• Martin Aigner e Günter M. Ziegler, Proofs from THE BOOK, traduzione di Silvia Quarterni, Milano, Springer, 2006, ISBN 88-470-0435-7.

Voci correlate

• Crivello di Eratostene
• Euclide
• Eulero
• Numero primo
• Piccolo teorema di Fermat
• Serie geometrica
• Dimostrazione della divergenza della serie dei reciproci dei primi

Collegamenti esterni

• (EN) Eric W. Weisstein, Teorema dell'infinità dei numeri primi, su MathWorld, Wolfram Research.

V · D · M Algebra
Numeri	Naturali · Interi · Razionali · Irrazionali · Algebrici · Trascendenti · Reali · Complessi · Numero ipercomplesso · Numero p-adico · Duali · Complessi iperbolici
Principi fondamentali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza · Relazione d'ordine · Associatività della potenza
Algebra elementare	Equazione · Disequazione · Polinomio · Triangolo di Tartaglia · Teorema binomiale · Teorema del resto · Lemma di Gauss · Teorema delle radici razionali · Regola di Ruffini · Criterio di Eisenstein · Criterio di Cartesio · Disequazione con il valore assoluto · Segno · Metodo di Gauss-Seidel · Polinomio simmetrico · Funzione simmetrica
Elementi di Calcolo combinatorio	Fattoriale · Permutazione · Disposizione · Combinazione · Dismutazione · Principio di inclusione-esclusione
Concetti fondamentali di Teoria dei numeri	Primi Numero primo · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Crivello di Atkin · Test di primalità · Teorema fondamentale dell'aritmetica Divisori Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Criteri di divisibilità · Divisore Aritmetica modulare Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Funzione φ di Eulero · Teorema di Wilson · Reciprocità quadratica
Teoria dei gruppi	Gruppi Gruppo (finito · ciclico · abeliano) · Gruppo primario · Gruppo quoziente · Gruppo nilpotente · Gruppo risolubile · Gruppo simmetrico · Gruppo diedrale · Gruppo semplice · Gruppo sporadico · Gruppo mostro · Gruppo di Klein · Gruppo dei quaternioni · Gruppo generale lineare · Gruppo ortogonale · Gruppo unitario · Gruppo unitario speciale · Gruppo residualmente finito · Gruppo spaziale · Gruppo profinito · Out(Fn) · Parola · Prodotto diretto · Prodotto semidiretto · Prodotto intrecciato Teoremi Alternativa di Tits · Teorema di isomorfismo · Teorema di Lagrange · Teorema di Cauchy · Teoremi di Sylow · Teorema di Cayley · Teorema di struttura dei gruppi abeliani finiti · Lemma della farfalla · Lemma del ping-pong · Classificazione dei gruppi semplici finiti Sottoinsiemi Sottogruppo · Sottogruppo normale · Sottogruppo caratteristico · Sottogruppo di Frattini · Sottogruppo di torsione · Classe laterale · Classe di coniugio · Serie di composizione Omomorfismo · Isomorfismo · Automorfismo interno · Automorfismo esterno · Permutazione · Presentazione di un gruppo · Azione di gruppo
Teoria degli anelli	Anello (artiniano · noetheriano · locale) · Caratteristica · Ideale (primo · massimale) · Dominio (a fattorizzazione unica · a ideali principali · euclideo) · Matrice · Anello semplice · Anello degli endomorfismi · Teorema di Artin-Wedderburn · Modulo · Dominio di Dedekind · Estensione di anelli · Teorema della base di Hilbert · Anello di Gorenstein · Base di Gröbner · Prodotto tensoriale · Primo associato
Teoria dei campi	Campo · Polinomio irriducibile · Polinomio ciclotomico · Teorema fondamentale dell'algebra · Campo finito · Automorfismo · Endomorfismo di Frobenius Estensioni Campo di spezzamento · Estensione di campi · Estensione algebrica · Estensione separabile · Chiusura algebrica · Campo di numeri · Estensione normale · Estensione di Galois · Estensione abeliana · Estensione ciclotomica · Teoria di Kummer Teoria di Galois Gruppo di Galois · Teoria di Galois · Teorema fondamentale della teoria di Galois · Teorema di Abel-Ruffini · Costruzioni con riga e compasso
Altre strutture algebriche	Magma · Semigruppo · Corpo · Spazio vettoriale · Algebra su campo · Algebra di Lie · Algebra differenziale · Algebra di Clifford · Gruppo topologico · Gruppo ordinato · Quasi-anello · Algebra di Boole
argomenti	Teoria delle categorie · Algebra lineare · Algebra commutativa · Algebra omologica · Algebra astratta · Algebra computazionale · Algebra differenziale · Algebra universale

V · D · M Teoria dei numeri
Numeri più usati	Naturali · Interi · Pari e dispari
Principi generali	Principio d'induzione · Principio del buon ordinamento · Relazione di equivalenza
Successioni di interi	Fattoriale · Successione di Fibonacci · Numero di Catalan · Numero di Perrin · Numero di Eulero · Successione di Mian-Chowla · Successione di Thue-Morse
Caratteristiche dei numeri primi	Numero primo · Lemma di Euclide · Teorema dell'infinità dei numeri primi · Crivello di Eratostene · Test di primalità · Teorema fondamentale dell'aritmetica · Interi coprimi · Identità di Bézout · MCD · mcm · Algoritmo di Euclide · Algoritmo esteso di Euclide · Teorema dei numeri primi
Funzioni aritmetiche	Funzione moltiplicativa · Funzione additiva · Convoluzione di Dirichlet · Funzione φ di Eulero · Funzione di Möbius · Funzione tau sui positivi · Funzione sigma · Funzione di Liouville · Funzione di Mertens
Aritmetica modulare	Teorema cinese del resto · Piccolo teorema di Fermat · Teorema di Eulero · Criteri di divisibilità · Teorema di Fermat sulle somme di due quadrati · Teorema di Wilson · Legge di reciprocità quadratica
Congetture	Congettura di Goldbach · Congettura di Polignac · Congettura abc · Congettura dei numeri primi gemelli · Congettura di Legendre · Nuova congettura di Mersenne · Congettura di Collatz · Ipotesi di Riemann
Altro	Problema di Waring
Principali teorici	Fibonacci · Fermat · Gauss · Eulero · Legendre · Riemann · Dirichlet
Discipline connesse	Teoria algebrica dei numeri · Teoria analitica dei numeri · Crittografia · Teoria computazionale dei numeri

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