Demostració d’Euclides de l’existència d’infinits nombres primers



Introducció: Fa més de 2200 anys, Euclides demostrà que existeixen infinits nombres primers.

No obstant, avui en dia, encara no sabem si existeix una fórmula general per poder determinar si un nombre és primer o no, i tampoc sabem una fórmula per saber quin és el nombre que ocupi la posició  (no sabem la fórmula ni sabem si existeix o no aquesta fórmula).

Tot i així, s’han trobat fórmules que retornen nombres primers (però no tots els nombres primers). També hem demostrat algoritmes per descartar “senzillament” si un nombre és o no primer (recorda: un nombre que acaba en  o  és divisible per  i per tant no és primer)...

És coneixen molts nombres primers, el més gran que s’ha trobat és 257,885,161 – 1, trobat per algoritmes informàtics.

Entre moltes altres coses, els primers s’utilitzen per encriptar (en particular un tipus d’encriptació anomenada asimètrica i molt difícil de poder tirar endarrera).

Recordem: Un nombre natural és primer, si i només si, només divisible per  i per ell mateix.
Així doncs, la taula dels nombres primers des del 1 fins al 100 és la que podeu veure a la dreta. Aquesta taula s’anomena Sedàs d’Erastòtenes (Eratòstenes de Cirere (276-194 aC) matemàtic de l'Antiga Grècia).

Incís: Un nombre és divisible per un altre si al fer la divisió té residu zero.

Teorema: Tot nombre natural, n, és pot descomposar de forma única com a producte finit de nombres primers,i.e. n=p1·p2·...·pS.

Corol·lari: Qualsevol nombre dividit per un dels seus factors té residu zero.




Proposició (Euclides):  El conjunt de nombres primers és infinit.

Demostració: Suposem que no, i.e. existeix un nombre finit de nombres primers. Aleshores els podem denotar. Sigui aquest conjunt :

P={p1, p2, ... pN}


Aleshores, qualsevol nombre natural ha de ser divisible per un nombre finit de productes d’aquests nombres.
Creem el següent nombre natural: 
q=p1·p2·...·pN+1

Aquest nombre pot ser primer o no.

Si és primer contradicció, !!, ja que és el producte de tots els primers més un, per tant un nou primer

Si no és primer, observem que també arribem a contradicció, perquè per dividir per qualsevol primer , p1, té com a residu 1 (és a dir, no és divisible per cap dels primers de la llista finita de primers)
Aleshores, al arribar a contradicció l’única suposició és la de que el conjunt sigui finit, per tant, per reducció a l’absurd podem afirmar: el conjunt de nombres primers és infinit.