Etiquetes

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

Introducció

Fa més de 2200 anys, Euclides va demostrar que existeixen infinits nombres primers.

Tot i això, encara avui no disposem d’una fórmula general que permeti determinar directament si un nombre qualsevol és primer o no. Tampoc coneixem una fórmula que permeti calcular quin és el nombre primer que ocupa la posició (n)-èssima de la successió de nombres primers; de fet, ni tan sols sabem si una fórmula d’aquest tipus existeix.

Malgrat aquestes dificultats, sí que s’han descobert fórmules capaces de generar alguns nombres primers (encara que no tots), així com algoritmes eficients que permeten descartar relativament fàcilment si un nombre és compost. Per exemple, qualsevol nombre acabat en (0) o (5) és divisible per (5) i, per tant, no és primer.

Actualment es coneixen nombres primers extremadament grans. Un dels més grans descoberts és: 257,885,161 – 1 trobat mitjançant algoritmes informàtics especialitzats.

Els nombres primers tenen una gran importància en matemàtiques i informàtica. Entre moltes altres aplicacions, s’utilitzen en sistemes d’encriptació, especialment en la criptografia asimètrica, fonamental en les comunicacions segures actuals.

Euclides

Demostració d'infinits primers

Definició: Un nombre natural és primer si i només si és divisible únicament per (1) i per ell mateix.

Així doncs, la taula de nombres primers entre (1) i (100) és la que es pot obtenir amb el conegut sedàs d’Eratòstenes, ideat per Eratòstenes de Cirene (276 aC – 194 aC).


Incís: Direm que un nombre és divisible per un altre quan, en efectuar la divisió, el residu és zero.


Teorema fonamental de l’aritmètica: Tot nombre natural (n) es pot descompondre de manera ú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 dels nombres primers és infinit.

Demostració: Suposem, per reducció a l’absurd, que el conjunt de nombres primers és finit. Així doncs, podem escriure:
P={p1, p2, ... pN}

On aquesta llista conté tots els nombres primers existents. 

Aleshores, qualsevol nombre natural hauria de poder expressar-se mitjançant productes d’aquests nombres primers.

Construïm ara el nombre següent:

q=p1 · p2 · ... · pN + 1


Aquest nombre pot ser primer o compost.
  • Si (q) és primer, arribem immediatament a una contradicció, ja que (q) seria un nombre primer que no apareix a la llista anterior.
  • Si (q) no és primer, aleshores hauria de ser divisible per algun dels nombres primers de la llista. Tanmateix, observem que en dividir (q) per qualsevol dels nombres (p_i), el residu és sempre (1). Per tant, (q) no és divisible per cap dels nombres primers de la llista.
Això torna a conduir a una contradicció.

Per tant, la suposició inicial (que el conjunt de nombres primers és finit) és falsa. En conseqüència, per reducció a l’absurd, podem afirmar que:
El conjunt dels nombres primers és infinit.


Enviar missatge per correu electrònic
Labels: