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.
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 q 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.
En pdf:
https://drive.google.com/file/d/1pEpxicrhDao8Pr9sAYf5vUAn0IoU1m86/view?usp=sharing