Teorema di Euclide - Euclid's theorem

Il teorema di Euclide è una dichiarazione fondamentale nella teoria dei numeri che afferma che ci sono infinitamente molte primi numeri. Fu dimostrato per la prima volta da Euclide nel suo lavoro Elements . Ci sono diverse dimostrazioni del teorema.

La prova di Euclide

Euclide ha offerto una prova pubblicata nella sua opera Elementi (Libro IX, Proposizione 20), che qui viene parafrasata.

Consideriamo una qualsiasi lista finita di numeri primi p ₁ ,  p ₂ , ...,  p _n . Si dimostrerà che esiste almeno un numero primo aggiuntivo non presente in questa lista. Sia P il prodotto di tutti i numeri primi della lista: P  =  p ₁ p ₂ ... p _n . Sia q  =  P  + 1. Allora q è primo o no:

• Se q è primo, allora c'è almeno un altro primo che non è nell'elenco, vale a dire q stesso.
• Se q non è primo, allora un fattore primo p divide  q . Se questo fattore p fosse nella nostra lista, allora dividerebbe P (poiché P è il prodotto di ogni numero nella lista); ma p divide anche P  + 1 =  q , come appena detto. Se p divide P e anche q, allora p deve dividere anche la differenza dei due numeri, che è ( P  + 1) −  P o solo 1. Poiché nessun numero primo divide 1, p non può essere nella lista. Ciò significa che esiste almeno un altro numero primo oltre a quelli nell'elenco.

Questo prova che per ogni lista finita di numeri primi c'è un numero primo non nella lista. Nel lavoro originale, poiché Euclide non aveva modo di scrivere un elenco arbitrario di numeri primi, usò un metodo che applicò frequentemente, cioè il metodo dell'esempio generalizzabile. Vale a dire, sceglie solo tre numeri primi e, usando il metodo generale descritto sopra, dimostra che può sempre trovare un numero primo aggiuntivo. Euclide presume presumibilmente che i suoi lettori siano convinti che una dimostrazione simile funzionerà, non importa quanti numeri primi siano stati scelti originariamente.

Spesso si dice erroneamente che Euclide abbia dimostrato questo risultato per assurdo partendo dal presupposto che l' insieme finito inizialmente considerato contenga tutti i numeri primi, sebbene in realtà sia una dimostrazione per casi , un metodo di dimostrazione diretta . Il filosofo Torkel Franzén , in un libro sulla logica, afferma: "La prova di Euclide che ci sono infiniti numeri primi non è una prova indiretta [...] L'argomento è talvolta formulato come una prova indiretta sostituendolo con l'assunzione 'Supponiamo che q ₁ , ... q _n sono tutti i numeri primi'. Tuttavia, poiché questa ipotesi non è nemmeno utilizzata nella dimostrazione, la riformulazione è inutile."

Variazioni

Esistono diverse variazioni sulla dimostrazione di Euclide, tra cui le seguenti:

Il fattoriale n ! di un intero positivo n è divisibile per ogni intero da 2 a n , in quanto è il prodotto di tutti loro. Quindi, n ! + 1 non è divisibile per nessuno degli interi da 2 a n , inclusi (dà un resto di 1 quando diviso per ciascuno). Quindi n ! + 1 è primo o divisibile per un primo maggiore di  n . In entrambi i casi, per ogni intero positivo n , esiste almeno un primo maggiore di  n . La conclusione è che il numero dei primi è infinito.

La prova di Eulero

Un'altra dimostrazione, del matematico svizzero Leonhard Euler , si basa sul teorema fondamentale dell'aritmetica : che ogni intero ha un'unica scomposizione in fattori primi. Ciò che ha scritto Eulero (non con questa notazione moderna e, a differenza degli standard moderni, non limitando gli argomenti in somme e prodotti a qualsiasi insieme finito di interi) è equivalente all'affermazione che abbiamo

${\displaystyle \prod _{p\in P_{k}}{\frac {1}{1-{\frac {1}{p}}}}=\sum _{n\in N_{k}}{ \frac {1}{n}},}$

dove denota l'insieme dei k primi numeri primi, ed è l'insieme degli interi positivi i cui fattori primi sono tutti in${\displaystyle P_{k}}$${\displaystyle N_{k}}$${\displaystyle P_{k}.}$

Per dimostrare questo, si espande ogni fattore nel prodotto come serie geometrica , e distribuisce il prodotto rispetto alla somma (questo è un caso particolare del prodotto di Eulero formula per la funzione zeta di Riemann ).

${\displaystyle {\begin{allineato}\prod _{p\in P_{k}}{\frac {1}{1-{\frac {1}{p}}}}&=\prod _{p\ in P_{k}}\sum _{i\geq 0}{\frac {1}{p^{i}}}\\&=\left(\sum _{i\geq 0}{\frac {1 }{2^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{3^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{5^{i}}}\right)\cdot \left(\sum _{i\geq 0}{\frac {1}{7^{i} }}\right)\cdots \\&=\sum _{\ell ,m,n,p,\ldots \geq 0}{\frac {1}{2^{\ell }3^{m}5^ {n}7^{p}\cdots }}\\&=\sum _{n\in N_{k}}{\frac {1}{n}}.\end{allineato}}}$

Nella penultima somma ogni prodotto dei numeri primi compare esattamente una volta, e quindi l'ultima uguaglianza è vera per il teorema fondamentale dell'aritmetica. Nel suo primo corollario a questo risultato, Eulero denota con un simbolo simile all '« infinito assoluto » e scrive che la somma infinita nell'enunciato è uguale al « valore » , a cui è dunque uguale anche il prodotto infinito ( nella terminologia moderna ciò equivale dire che la somma parziale a della serie armonica diverge asintoticamente come ). Poi nel suo secondo corollario Eulero osserva che il prodotto ${\displaystyle \infty}$${\displaystyle \log \infty}$${\displaystyle x}$${\displaystyle \log x}$

${\displaystyle \prod _{n\geq 2}{\frac {1}{1-{\frac {1}{n^{2}}}}}}$

converge al valore finito 2, e che di conseguenza vi sono più numeri primi che quadrati (« sequitur infinities plures esse numeros primos »). Questo dimostra il teorema di Euclide.

Simbolo usato da Eulero per denotare l'infinito

Nello stesso articolo (Teorema 19) Eulero infatti utilizzò l'uguaglianza di cui sopra per dimostrare un teorema molto più forte che era sconosciuto prima di lui, ovvero che la serie

${\displaystyle \sum _{p\in P}{\frac {1}{p}}}$

è divergente , dove P denota l'insieme di tutti i numeri primi (Eulero scrive che la somma infinita , che nella terminologia moderna equivale a dire che la somma parziale a di questa serie si comporta asintoticamente come ). ${\displaystyle =\log\log\infty}$${\displaystyle x}$${\displaystyle \log \log x}$

La prova di Erdős

Paul Erdős ha fornito una dimostrazione che si basa anche sul teorema fondamentale dell'aritmetica. Ogni intero positivo ha una fattorizzazione unica in un numero quadrato libero e un numero quadrato rs ² . Ad esempio, 75.600 = 2 ⁴ 3 ³ 5 ² 7 ¹ = 21 ⋅ 60 ² .

Sia N un intero positivo e sia k il numero di primi minori o uguali a N . Chiamiamo quei primi p ₁ , ... , p _k . Qualsiasi numero intero positivo minore o uguale a N può quindi essere scritto nella forma

${\displaystyle \left(p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}\right)s^{2}, }$

dove ogni e _i è 0 o 1 . Ci sono 2 ^k modi per formare la parte priva di quadrati di a . E s ² può essere al massimo N , quindi s ≤ √ N . Pertanto, in questa forma possono essere scritti al massimo 2 ^k √ N numeri. In altre parole,

${\displaystyle N\leq 2^{k}{\sqrt {N}}.}$

Oppure, riordinando, k , il numero di primi minori o uguali a N , è maggiore o uguale a 1/2log ₂ N . Poiché N era arbitrario, k può essere grande quanto desiderato scegliendo N in modo appropriato.

La dimostrazione di Furstenberg

Negli anni '50, Hillel Furstenberg introdusse una dimostrazione per assurdo utilizzando la topologia puntuale .

Definire una topologia sul interi Z , chiamato topologia degli interi equispaziati , dichiarando un sottoinsieme U  ⊆  Z essere un insieme aperto se e solo se il biocida è insieme vuoto , ∅, o è un'unione di sequenze aritmetica S ( a ,  b ) (per a  0), dove

${\displaystyle S(a,b)=\{an+b\mid n\in \mathbb {Z} \}=a\mathbb {Z} +b.}$

Allora una contraddizione segue dalla proprietà che un insieme finito di interi non può essere aperto e la proprietà che gli insiemi di base S ( a ,  b ) sono sia aperti che chiusi , poiché

${\displaystyle \mathbb {Z} \setminus \{-1,+1\}=\bigcup _{p\mathrm {\,prime} }S(p,0)}$

non può essere chiuso perché il suo complemento è finito, ma è chiuso poiché è un'unione finita di insiemi chiusi.

Alcune prove recenti

Dimostrazione che utilizza il principio di inclusione-esclusione

Juan Pablo Pinasco ha scritto la seguente dimostrazione.

Siano p ₁ , ...,  p _N i più piccoli N primi. Allora per il principio di inclusione-esclusione , il numero di interi positivi minori o uguali a x che sono divisibili per uno di quei primi è

${\displaystyle {\begin{allineato}1+\sum _{i}\left\lfloor {\frac {x}{p_{i}}}\right\rfloor -\sum _{i<j}\left\ lfloor {\frac {x}{p_{i}p_{j}}}\right\rfloor &+\sum _{i<j<k}\left\lfloor {\frac {x}{p_{i}p_ {j}p_{k}}}\right\rfloor -\cdots \\&\cdots \pm (-1)^{N+1}\left\lfloor {\frac {x}{p_{1}\cdots p_{N}}}\right\rfloor .\qquad (1)\end{allineato}}}$

Dividendo per x e lasciando x  → ∞ dà

${\displaystyle \sum _{i}{\frac {1}{p_{i}}}-\sum _{i<j}{\frac {1}{p_{i}p_{j}}}+\ sum _{i<j<k}{\frac {1}{p_{i}p_{j}p_{k}}}-\cdots \pm (-1)^{N+1}{\frac {1 }{p_{1}\cdots p_{N}}}.\qquad (2)}$

Questo può essere scritto come

${\displaystyle 1-\prod _{i=1}^{N}\left(1-{\frac {1}{p_{i}}}\right).\qquad (3)}$

Se non esistono altri primi oltre a p ₁ , ...,  p _N , allora l'espressione in (1) è uguale a  e l'espressione in (2) è uguale a 1, ma chiaramente l'espressione in (3) non è uguale a 1. Pertanto, devono esserci più numeri primi di   p ₁ , ...,  p _N . ${\displaystyle \lfloor x\rfloor }$

Dimostrazione con la formula di de Polignac

Nel 2010, Junho Peter Whang ha pubblicato la seguente dimostrazione per assurdo. Sia k un qualsiasi numero intero positivo. Allora secondo la formula di de Polignac (in realtà dovuta a Legendre )

${\displaystyle k!=\prod _{p{\text{ primo}}}p^{f(p,k)}}$

dove

${\displaystyle f(p,k)=\left\lfloor {\frac {k}{p}}\right\rfloor +\left\lfloor {\frac {k}{p^{2}}}\right\ rfloor +\cdots .}$

${\displaystyle f(p,k)<{\frac {k}{p}}+{\frac {k}{p^{2}}}+\cdots ={\frac {k}{p-1} }\leq k.}$

Ma se esistono solo un numero finito di numeri primi, allora

${\displaystyle \lim _{k\to \infty }{\frac {\left(\prod _{p}p\right)^{k}}{k!}}=0,}$

(il numeratore della frazione crescerebbe singolarmente in modo esponenziale mentre per l'approssimazione di Stirling il denominatore crescerebbe più velocemente che singolarmente in modo esponenziale), contraddicendo il fatto che per ogni k il numeratore è maggiore o uguale al denominatore.

Dimostrazione per costruzione

Filip Saidak ha dato la seguente prova per costruzione , che non fa uso di reductio ad absurdum o Lemma di Euclide (che se un primo p divide ab allora deve dividere una o  B ).

Poiché ogni numero naturale (> 1) ha almeno un fattore primo e due numeri successivi n e ( n  + 1) non hanno fattori in comune, il prodotto n ( n  + 1) ha più fattori primi diversi del numero n stesso . Quindi la catena dei numeri pronici :
1×2 = 2 {2}, 2×3 = 6 {2, 3}, 6×7 = 42 {2, 3, 7}, 42×43 = 1806 {2, 3, 7, 43}, 1806×1807 = 3263442 {2, 3, 7, 43, 13, 139}, · · ·
fornisce una sequenza di insiemi crescenti illimitati di numeri primi.

Dimostrazione usando l'irrazionalità di π

Rappresentando la formula Leibniz per π come un prodotto di Eulero dà

${\displaystyle {\frac {\pi }{4}}={\frac {3}{4}}\times {\frac {5}{4}}\times {\frac {7}{8}}\ volte {\frac {11}{12}}\times {\frac {13}{12}}\times {\frac {17}{16}}\times {\frac {19}{20}}\times { \frac {23}{24}}\times {\frac {29}{28}}\times {\frac {31}{32}}\times \cdots}$

I numeratori di questo prodotto sono i numeri primi dispari e ogni denominatore è il multiplo di quattro più vicino al numeratore.

Se ci fossero un numero finito di numeri primi questa formula mostrerebbe che π è un numero razionale, contraddicendo il fatto che π è irrazionale .

Dimostrazione usando la teoria dell'informazione

Alexander Shen ha presentato una dimostrazione che utilizza l' incomprimibilità :

Supponiamo che ci fossero solo k primi ( p ₁ ...  p _k ). Per il teorema fondamentale dell'aritmetica , ogni intero positivo n potrebbe quindi essere rappresentato come:

${\displaystyle n={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}\cdots {p_{k}}^{e_{k}},}$

dove gli esponenti interi non negativi e _i insieme all'elenco di numeri primi di dimensione finita sono sufficienti per ricostruire il numero. Poiché per ogni i , segue che all (dove denota il logaritmo in base 2). ${\displaystyle p_{i}\geq 2}$${\displaystyle e_{i}\leq \lg n}$${\displaystyle \lg}$

Ciò produce una codifica per n della seguente dimensione (usando la notazione O grande ):

${\displaystyle O({\text{dimensione lista primaria}}+k\lg \lg n)=O(\lg \lg n)}$ bit.

Questa è una codifica molto più efficiente rispetto alla rappresentazione di n direttamente in binario, che richiede bit. Un risultato stabilito nella compressione dei dati senza perdita di dati afferma che generalmente non è possibile comprimere N bit di informazioni in meno di N bit. La rappresentazione sopra lo viola di gran lunga quando n è abbastanza grande poiché . ${\displaystyle N=O(\lg n)}$${\displaystyle \lg \lg n=o(\lg n)}$

Pertanto, il numero di numeri primi non deve essere finito.

Risultati più forti

I teoremi in questa sezione implicano simultaneamente il teorema di Euclide e altri risultati.

Teorema di Dirichlet sulle progressioni aritmetiche

Il teorema di Dirichlet afferma che per qualsiasi due interi coprimi positivi a e  d , ci sono infiniti primi della forma a  +  nd , dove n è anche un intero positivo. In altre parole, esistono infiniti numeri primi congruenti a un modulo d .

Teorema dei numeri primi

Sia π ( x ) la funzione di conteggio dei primi che fornisce il numero di primi minori o uguali a x , per qualsiasi numero reale  x . Il primo numero teorema precisa poi che x / log x è una buona approssimazione di π ( x ) , nel senso che il limite del quoziente delle due funzioni ¸ ( x ) e x / log x come x aumenta senza limite è 1 :

${\displaystyle \lim _{x\rightarrow \infty }{\frac {\pi (x)}{x/\ln(x)}}=1.}$

Usando la notazione asintotica questo risultato può essere riformulato come

${\displaystyle \pi (x)\sim {\frac {x}{\log x}}.}$

Questo produce il teorema di Euclide, poiché ${\displaystyle \lim _{x\rightarrow \infty }{\frac {x}{\log x}}=\infty.}$

Teorema di Bertrand-Chebyshev

In teoria dei numeri , il postulato di Bertrand è un teorema che afferma che per ogni intero esiste sempre almeno un numero primo tale che ${\displaystyle n>1}$

${\displaystyle n<p<2n.}$

Il teorema di Bertrand-Chebyshev può anche essere affermato come una relazione con , dove è la funzione di conteggio dei primi (numero di primi minore o uguale a ): ${\displaystyle \pi(x)}$${\displaystyle \pi(x)}$${\displaystyle x\,}$

${\displaystyle \pi (x)-\pi ({\tfrac {x}{2}})\geq 1,}$ per tutti ${\displaystyle x\geq 2.}$

Questa affermazione fu congetturata per la prima volta nel 1845 da Joseph Bertrand (1822-1900). Bertrand stesso ha verificato la sua affermazione per tutti i numeri nell'intervallo [2, 3 × 10 ⁶ ]. La sua congettura fu completamente dimostrata da Chebyshev (1821-1894) nel 1852 e quindi il postulato è anche chiamato teorema di Bertrand-Chebyshev o teorema di Chebyshev .

Note e riferimenti

link esterno

• Weisstein, Eric W. "Teorema di Euclide" . MathWorld .
• Elementi di Euclide, Libro IX, Prop. 20 (dimostrazione di Euclide, sul sito web di David Joyce alla Clark University)