1.25: Pruebas de Primalidad

Dos teoremas del capítulo anterior, el teorema de Wilson y el pequeño teorema de Fermat, conectan números primos y congruencias de maneras quizás sorprendentes. En este capítulo nos fijamos en cómo estos teoremas pueden convertirse en técnicas para probar si un número\(n\) es primo. Esas pruebas diferirán bastante de los primeros medios más simples de probar los primos que describimos a continuación, que se basa en la Sección 1.11 y específicamente en el Teorema 1.11.2:

Prueba de Primalidad #1

Dado un número entero\(n \geq 2\), determine si\(n\) es divisible por cualquier número entero en\(2,\dots,\lfloor\sqrt{n}\rfloor\) (más específicamente, por cualquier número primo en este rango). Si es así, entonces no\(n\) es primo; de lo contrario,\(n\) es primo.

Ahora usamos los teoremas del último capítulo.

Una prueba de primalidad usando el teorema de Wilson

Para presentar nuestra próxima prueba, observe lo siguiente.

• Si\(n\) es primo, entonces\((n-1)! \equiv -1 \pmod n\) (este es el Teorema de Wilson).
• Si\(n=4\), entonces\((n-1)!\equiv 1 \pmod n\); si en cambio\(n \neq 4\) pero no\(n\) es primo, entonces\((n-1)! \equiv 0 \pmod n\) (ver Ejercicio 1.24.1).

Por lo tanto, un entero\(n \geq 2\) es primo si y solo si\((n-1)! \equiv -1 \pmod n\). Esto nos da una prueba.

Prueba de Primalidad #2

Dado un número entero\(n \geq 2\), determinar si\((n-1)! \equiv -1 \pmod n\). Si es así,\(n\) es primo; si no, entonces\(n\) es compuesto.

Por ejemplo,\(4! = 24\), que es congruente con el\(-1\) módulo 5, por lo que esta prueba garantiza que\(5\) es primo; mientras tanto,\(11! = 39916800 \equiv 0 \pmod {12}\), por lo que la prueba muestra que no\(12\) es un número primo.

Un gran inconveniente de Primality Test #2 es que no parece haber una forma generalmente aplicable para computar eficientemente el\((n-1)!\) módulo\(n\) para grandes\(n\). Por ejemplo\(15!\) redondea a\(1.3076744\times 10^{12}\), y\(20!\) redondea a\(2.432902 \times 10^{18}\); los números factoriales\(n!\) son muy grandes incluso para relativamente pequeños\(n\). Podemos calcular reduciendo módulo\(n\) después de cada multiplicación;\((n-1)! \bmod n\) por ejemplo, calculamos\(8! \mod 9\) por\[\begin{aligned} 1 \bmod 9 &= 1;\\ (2\cdot 1) \bmod 9 &= 2;\\ (3\cdot 2\cdot 1) \bmod 9 &= (3 \cdot 2)\bmod 9 = 6;\\ (4 \cdot 3\cdot 2\cdot 1) \bmod 9 &= (4 \cdot 6)\bmod 9 = 6;\\ (5 \cdot 4 \cdot 3 \cdot 2 \cdot 1) \bmod 9 &= (5 \cdot 6)\bmod 9 = 3;\\ (6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1) \bmod 9 &= (6 \cdot 3)\bmod 9 = 0;\\ (7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1) \bmod 9 &= (7 \cdot 0)\bmod 9 = 0;\\ (8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1) \bmod 9 &= (8 \cdot 0)\bmod 9 = 0.\end{aligned}\] Sin embargo, tenga en cuenta que cada línea de dicho cálculo requiere una multiplicación más y una aplicación más de “mod”. De ahí que probar si\((n-1)! \equiv -1 \pmod n\) de esta manera toma una serie de pasos que es proporcional a\(n\), de manera que a medida que\(n\) se hace cada vez más grande, esperaríamos que esta prueba de primalidad tardaría cada vez más en realizarse (ya sea realizada por un ser humano o un computadora).

En contraste, tenga en cuenta que el número de pasos necesarios para llevar a cabo la Prueba de Primalidad #1 es proporcional a\(\sqrt{n}\), por lo que la Prueba de Primalidad #1 puede tardar menos tiempo en aplicarse que la Prueba de Primalidad #2, especialmente si\(n\) es grande. De ahí que el Teorema de Wilson, si bien nos da una nueva prueba de primalidad, no nos ha dado una gran prueba de primalidad.

Nos preguntamos, ¿podemos encontrar una prueba aún mejor para la primalidad?

Una prueba de primalidad usando el pequeño teorema de Fermat

Según el pequeño teorema de Fermat, si\(p\) es primo y\(1\le a\le p-1\), entonces\[a^{p-1}\equiv 1\pmod p.\nonumber \] Lo contrario también es cierto en el siguiente sentido:

Teorema \(\PageIndex{1}\): Fermat's Little Theorem Converse

Si\(m\ge 2\) y por todos los\(a\) tales que\(1\le a\le m-1\) tenemos\[a^{m-1}\equiv 1\pmod m\nonumber \] entonces\(m\) debe ser primar.

Prueba

Si la hipótesis se mantiene, entonces para todos\(a\) con\(1\le a\le m-1\), sabemos que\(a\) tiene un módulo inverso\(m\), es decir,\(a^{m-2}\) es un inverso para\(a\) módulo\(m\). Por Teorema 1.20.2, esto dice que para\(1\le a\le m-1\),\(\gcd(a,m)=1\). Pero si no\(m\) fueran primos, entonces tendríamos\(m=ab\) con\(1<a<m\),\(1<b<m\). Entonces\(\gcd(a,m)=a>1\), una contradicción. Entonces\(m\) debe ser prime.

Podemos convertir esto en una prueba de primalidad.

Prueba de Primalidad #3

Dado un entero\(n \geq 2\), para cada uno\(a\) entre\(1\) y\(n-1\), probar si\(a^{n-1}\equiv 1 \pmod n\). Si la congruencia es verdadera para cada valor de\(a\), entonces\(n\) es primo. Si la congruencia falla por algún valor de\(a\) entre\(1\) y\(n-1\), entonces no\(n\) es primo.

Como ejemplo, usando Primality Test #3 para decidir si 13 es primo, verificaríamos lo siguiente:

\(1^{12} = 1 \equiv 1 \pmod {13}\);		\(7^{12} = 13841287201 \equiv 1 \pmod {13}\);
\(2^{12} = 4096 \equiv 1 \pmod {13}\);		\(8^{12} = 68719476736 \equiv 1 \pmod {13}\);
\(3^{12} = 531441 \equiv 1 \pmod {13}\);		\(9^{12} = 282429536481 \equiv 1 \pmod {13}\);
\(4^{12} = 16777216 \equiv 1 \pmod {13}\);		\(10^{12} = 1000000000000 \equiv 1 \pmod {13}\);
\(5^{12} = 244140625 \equiv 1 \pmod {13}\);		\(11^{12} = 3.1384284... \times 10^{12} \equiv 1 \pmod {13}\);
\(6^{12} = 2176782336 \equiv 1 \pmod {13}\);		\(12^{12} = 8.9161004... \times 10^{12} \equiv 1 \pmod {13}\).

Pruebas de Primalidad Usando el Pequeño Teorema de Fermat, Continuación

Usando Primality Test #3 para verificar que\(p\) es prime, tendríamos que verificarlo\(a^{p-1}\equiv 1\pmod{p}\) para\(a=1,2,3,\dotsc,p-1\). Como mostró el último ejemplo, esto es mucho trabajo.

\(n>2\)Y si y eso lo sabíamos\(2^{n-1}\equiv 1\pmod n\), aunque no sabíamos lo que\(a^{n-1}\) era congruente al módulo\(n\) para otros valores de\(a\)? ¿Podríamos concluir que\(n\) fue primo?

Desafortunadamente, la respuesta es no. Por ejemplo, mira\(n=341\). Este número no es primo (¿por qué no?). Aún así, es cierto que\(2^{341-1}\equiv 1\pmod {341}\) (ver Ejercicio\(\PageIndex{1}\)).

La moraleja es que aunque\(2^{n-1}\equiv 1\pmod n\), el número no\(n\) necesita ser primo. \(^{1}\)Para estar absolutamente seguros de que\(n\) era primo usando el pequeño teorema y teorema de Fermat\(\PageIndex{1}\), tendríamos que verificar si\(a^{n-1}\equiv 1\pmod n\) para todos los enteros\(a\) en\(2,3,\dots,n-1\).

Por otro lado, considere el caso de\(m=63\). Tenga en cuenta que\[2^6=64\equiv 1\pmod{63}.\nonumber \]

De ahí,\(2^6\equiv 1\pmod{63}\). Elevando ambos lados al\(10\) th poder que tenemos\[2^{60}\equiv 1\pmod{63}.\nonumber \] Luego multiplicando ambos lados por\(2^2\) obtenemos\[2^{62}\equiv 4\pmod{63}.\nonumber \] Ya que\[4\not\equiv 1\pmod{63},\nonumber \] tenemos\[2^{62}\not\equiv 1\pmod{63}.\nonumber \] Esto nos dice que no\(63\) es primo, sin factorizar \(63\). Destacamos que en general si\(2^{m-1} \not\equiv 1 \pmod m\) entonces podemos estar seguros de que no\(m\) es primo.

¿Podemos convertir esto en una prueba (o prueba parcial) de primalidad? Veamos algunos datos experimentales.

HECHO.

Hay\(455\),\(052\), primos\(511\) impares\(p\le 10^{10}\), todos los cuales satisfacen\(2^{p-1}\equiv 1\pmod p\). Solo hay\(14\), números\(884\) compuestos\(2<n\le 10^{10}\) que satisfacen\(2^{n-1}\equiv 1\pmod n\). Así, si\(2<n\le 10^{10}\) y\(n\) satisface\(2^{n-1}\equiv 1\pmod n\), la probabilidad de que\(n\) sea primo es\[\frac{455,052,511}{455,052,511+14,884}\approx .999967292.\nonumber \] En otras palabras, si lo encuentras\(2^{n-1}\equiv 1\pmod n\), entonces es muy probable (pero no una certeza) que\(n\) sea prime, al menos cuando\(n\le 10^{10}\).

Así, a diferencia de las tres pruebas de primalidad anteriores en este capítulo, nuestra siguiente prueba de primalidad es una prueba probabilística de primalidad.

Prueba de Primalidad #4

Dado un entero\(n > 2\), pruebe si\(2^{n-1}\equiv 1 \pmod n\). Si no, entonces\(\underline{\text{definitely}}\) no\(n\) es primo. Si\(2^{n-1}\equiv 1 \pmod n\), entonces\(n\) es\(\underline{\text{probably}}\) primo.

Uno podría preguntarse qué pasa si usamos 3 en lugar de 2 en la prueba probabilística de primalidad anterior. O, mejor aún, ¿y si evaluamos\(a^{m-1} \bmod m\) para varios valores diferentes de\(a\). Considere los siguientes datos:

• El número de primos\(p\le 10^6\) es 78,498.
• El número de números compuestos\(n\le 10^6\) tal que\(2^{n-1}\equiv 1\pmod n\) es\(245\).
• El número de números compuestos\(n\le 10^6\) tal que\(2^{n-1}\equiv 1\pmod n\) \(\underline{\text{and}}\)\(3^{n-1}\equiv 1\pmod n\) es 66.
• El número de números compuestos\(n\le 10^6\) tal que\(a^{n-1}\equiv 1\pmod n\) para\(\underline{\text{all}}\)\(a \in \{2,3,5,7,11,13,17,19,31,37,41\}\) es 0.

Haciendo una pausa aquí, tenemos la otra prueba probabilística de primalidad, más elaborada que la anterior:

Prueba de Primalidad #5

Dado un entero\(n > 2\), pruebe si\(a^{n-1}\equiv 1\pmod n\) para\(a\in\{2,3,5,7,11,13,17,19,31,37,41\}\) tal que\(n \nmid a\). Si las congruencias no son ciertas para todos estos\(a\), entonces\(\underline{\text{definitely}}\) no\(n\) es primo. Si las congruencias son todas verdaderas, entonces\(n\) es\(\underline{\text{definitely}}\) prime if\(n\le 10^6\) y\(\underline{\text{probably}}\) prime (altamente probable) if\(n >10^6\).

Conclusión

En la práctica, existen mejores pruebas probabilísticas de primalidad que las mencionadas en este capítulo, utilizando enfoques más eficientes que nuestras aplicaciones del Teorema de Wilson y el Pequeño Teorema de Fermat. Para más detalles véase, por ejemplo, Teoría de Números Elementales, cuarta edición, de Kenneth Rosen.

Sistemas de álgebra computacional como Maple ejecutan pruebas de primalidad probabilística muy sofisticadas (los cálculos para los números\(n \leq 10^6\) anteriores se calcularon usando Maple). Por ejemplo, el comando isprime (n) de Maple devuelve false si no\(n\) es primo y devuelve true si probablemente\(n\) es primo. (La prueba de primalidad subyacente utilizada por isprime utiliza una idea algo diferente a la de nuestras pruebas probilistas anteriores.) Si bien idealmente nos gustaría eliminar toda incertidumbre de los resultados de una prueba como isprime (n), hasta ahora nadie ha encontrado un entero\(n\) para el que isprime (n) da la respuesta incorrecta.

En este capítulo, nuestras tres primeras pruebas de primalidad dieron respuestas definitivas pero dieron muchos pasos para completar. Las pruebas de primalidad en el último apartado dieron respuestas probables, pero no siempre ciertas, utilizando mucho menos trabajo. \(^{2}\)En teoría es posible eliminar toda incertidumbre de nuestra prueba de primalidad utilizando un algoritmo que requiere un número de pasos proporcional al número de dígitos en\(n\) (recordar del Ejercicio 1.6.11 que el número de dígitos en \(n\)es proporcional a\(\log n\)). Esto es mediante el uso de la prueba de primalidad Agrawal—Kayal-Saxena, o AKS, que se publicó en 2002 y obtuvo a sus autores múltiples premios de prestigio, ya que fue la primera prueba de primalidad en lograr todo lo que hace. Tenga en cuenta que la prueba AKS es de gran importancia teórica, pero en la práctica no se usa mucho en absoluto, hay formas mucho más eficientes de probar la primalidad de\(n\).

Terminamos este capítulo con una invitación: Investiga un poco por tu cuenta, en línea o de otra manera... ¿Qué puedes averiguar sobre el estado actual del arte en las pruebas de primalidad?

Ejercicios

Ejercicio \(\PageIndex{1}\)

Use una computadora (o hágalo a mano y/o calculadora) para verificar eso\(2^{340} \equiv 1 \pmod {341}\) y que 341 no es primo. (Pista: para cálculos más rápidos, comience por determinar\(2^{10}\bmod 341\).)

Ejercicio\(\PageIndex{2}\)

Use una computadora (o hágalo a mano y/o calculadora) para mostrar que

1. \(3^{90}\equiv 1\pmod{91}\), pero no\(91\) es primo.
2. \(2^{n-1}\equiv 1\pmod n\)y\(3^{n-1}\equiv 1\pmod n\) para\(n=1105\), pero no\(1105\) es primo.

(Pista: tenga en cuenta que\(a^k\equiv 1\pmod n \ \ \Leftrightarrow \ \ a^k\bmod n=1\).)

Ejercicio\(\PageIndex{3}\)

Demostrar las cinco pruebas de primalidad de este capítulo utilizando el número\(n=11\), mostrando todos los cómputos y la determinación de cada prueba. Después repita estas mismas cinco pruebas para\(n=12\).

Notas al pie

[1] Si\(n\) es compuesto pero\(a^{n-1}= 1\)\((\pmod n)\) para algunos\(a\) que es relativamente primo a\(n\), llamamos\(n\) un Fermat pseudoprimo.

[2] Una cosa que no hemos comentado es la cantidad de trabajo que implica elevar un entero\(a\) a un exponente alto como\(n-1\), cuando\(n\) es grande. Esto resulta que necesita menos trabajo de lo que piensas. ¡Estén atentos para el próximo capítulo!