Números pseudoprimos

Fecha de primera versión: Diciembre 1997
Fecha de última actualización: 19/04/2010

Esta página esta basada en un post de Merlín en la news es.ciencia.matematica.

Se llaman números pseudoprimos los números que parecen primos pero no lo son.

La única forma certera de determinar si un número es primo es dividir por todos los anteriores (bueno, podríamos apañarnos para quitar algunos números que sabemos no son primos, los pares, los terminados en 5, etc.) y comprobar que el resto no es cero en ninguno de ellos. Cuando el número es muy grande, este proceso es inviable, incluso con potentes ordenadores, por eso se utilizan métodos probabilísticos. Si el número cumple la prueba y no es primo, se dice que ese número es pseudoprimo.

Por ejemplo, si decimos que todos los primos son de la forma 6n+5, y el numero elegido es el 35, diremos que 35 es un pseudoprimo porque cumple la condición 6n+5 y no es primo.

Una de las pruebas mas aplicadas es el del pequeño teorema de Fermat, que dice que si p es primo, entonces para cualquier b se verifica que b^p-1 = 1 mod p. La manera de comprobar esto es cogiendo un b cualquiera y comprobar si se verifica el teorema. Sin embargo, no supone ninguna garantía, desde luego si no lo verifica, podemos afirmar que el número es compuesto, pero si lo verifica, no podemos afirmar con seguridad que sea primo. Si nos dan el número 91 y elegimos b (que llamamos base) igual a 3 se verifica, se cumple la prueba, pero sin embargo, 91 no es primo. Por el contrario, si elegimos como base 2, no lo verifica, por lo tanto no es primo, por eso decimos que es pseudoprimo de base 3.

Si elegimos un número b, entre 1 y p, tenemos una probabilidad de 1/2 de que sea primo, si elegimos dos números la probabilidad es de 1/4 y así sucesivamente. Por lo tanto, tenemos un método probabilístico, que lo único que nos dice con seguridad es si el número es compuesto.

Hay unos números que sin ser primos, pasan la prueba para todas las bases entre 1 y p, son los números de Carmichael (el más pequeño es el 561). Sólo hay 2163 números de Carmichael menores de 25 000 000 000 y sólo 16 (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973 y 75361) son menores de 100 000. 

También existen los pseudoprimos de Euler y los pseudoprimos fuertes.