Teorema d'Euclides

Euclides

En aritmètica, el teorema d'Euclides sobre els nombres primers afirma:

Teorema d'Euclides Existeix una infinitat de nombres primers

El teorema rep el seu nom en honor d'Euclides qui va proporcionar la primera demostració escrita que es coneix d'aquest resultat a la proposició 20 del llibre IX dels elements.

«	Proposició 20. Hi ha més nombres primers que qualsevol quantitat proposada de nombres primers.	»
— Euclides

Hi ha diverses demostracions.

Demostració d'Euclides

En els seus Elements, Euclides demostra que de tres nombres primers diferents se'n pot ser deduït un quart. La demostració es generalitza immediatament a tota enumeració finita de nombres primers. Dedueix que de nombres primers n'hi ha una quantitat més gran que tota quantitat finita. L'infinit que s'evidencia en aquesta prova és doncs un "infinit potencial", compatible amb la doctrina aristotèlica.

Actualitzada, la seva demostració es presenta com segueix: suposem que p₁,p₂,p₃,...,p_n sigui una llista finita de nombres primers diferents. Si N designa el seu producte, els nombres primers ja enumerats no poden dividir N+1; ara bé, tot nombre posseeix un factor primer, per tant existeix un nombre primer que no forma part de la successió donada. El resultat segons el qual tot nombre posseeix un factor primer es demostra en la proposició 20 llibre IX dels Elements, avui en dia es desprèn directament del teorema fonamental de l'aritmètica.

L'argumentació emprada per Euclides permet construir per recurrència una successió injectiva (p_n) de nombres primers: p_n es defineix com el factor primer més petit de $\prod _{k<n}p_{k}+1.$.

Com senyala Gérald Tenenbaum, la demostració d'Euclides «és massa senzilla per ser efectiva» (en el sentit de caracteritzar l'abundància de nombres primers en el conjunt dels nombres naturals, en el sentit de demostrar que n'hi ha infinits és perfectament efectiva). De fet, la construcció mostra que l'enèsim nombre primer p_n és inferior o igual a $2^{2^{n}}$.

Demostració d'Euler

Euler

El matemàtic suís Leonhard Euler va proposar una altra demostració. Aquesta demostració es recolza en el teorema fonamental de l'aritmètica. Si P designa el conjunt dels nombres primers, Euler escriu:

$\prod _{p\in P}{\frac {1}{1-1/p}}=\prod _{p\in P}\sum _{k\geq 0}{\frac {1}{p^{k}}}=\sum _{n}{\frac {1}{n}}$

S'utilitzen per això la suma d'una sèrie geomètrica i el desenvolupament (únic) en factors primers d'un nombre natural (en altres paraules, el teorema fonamental de l'aritmètica). Llavors la divergència de la sèrie harmònica demostra que la suma (de la dreta) tendeix cap a l'infinit: per tant el producte (de l'esquerra) no pot ser finit, hi ha per tant una infinitat de nombres primers.

Teorema de la progressió aritmètica de Dirichlet

Article principal: Teorema de la progressió aritmètica de Dirichlet

El teorema de Dirichlet generalitza el resultat d'Euclides: afirma que hi ha una infinitat de nombres primers de la forma ak + n, on a i n són enters fixats, primers entre ells. En altres paraules, existeix una infinitat de nombres primers en tota progressió aritmètica.

El teorema d'Euclides correspon en cas particular de a = 1. Existeixen demostracions elementals per a certs casos particulars del teorema de Dirichlet, però la demostració completa, que s'inspira en la d'Euler per al teorema d'Euclides, es basa en arguments avançats d'anàlisi.

Teorema dels nombres primers

Article principal: Teorema dels nombres primers

Aquest teorema, conjecturat al començament del segle xix i demostrat el 1896, de manera simultània i independentment per Jacques Hadamard i Charles-Jean de la Vallée Poussin, precisa la repartició dels nombres primers. Sigui $\pi (x)$ la quantitat de nombres primers inferiors a un nombre x, el teorema d'Euclides diu que $\pi (x)$ tendeix cap a l'infinit quan x creix. El teorema dels nombres primers precisa que la quantitat $\pi (x)/x$ tendeix cap a $1/{\log(x)}$ quan x creix.

Altrament dit, la quantitat de nombres primers és de l'ordre de magnitud de $n\log(n)$.

La demostració original fa servir nocions delicades d'anàlisi complexa, en particular la Funció zeta de Riemann. Però hi ha demostracions més elementals.

Vegeu també

• Nombre primer
• Euclides