El Recíproco de Wilson para Primalidad

Teoría

El Recíproco de Wilson es la implicación inversa del conocido Teorema de Wilson. Mientras que el Teorema de Wilson dice que para cada primo $p$, $(p-1)! \equiv -1 \pmod p$, el recíproco afirma que si la congruencia $(n-1)! \equiv -1 \pmod n$ se cumple para un entero $n > 1$, entonces $n$ tiene que ser primo. Juntos, el teorema y su recíproco te dan una condición necesaria y suficiente para la primalidad: un entero $n > 1$ es primo si y solo si $(n-1)! \equiv -1 \pmod n$.

Este concepto es muy importante en la teoría porque establece una prueba de primalidad definitiva basada en aritmética modular. Pero, en la práctica, no es nada eficiente para valores de $n$ grandes porque calcular $(n-1)!$ requiere $O(n)$ multiplicaciones, lo cual es mucho más lento que la división por tentativa o pruebas probabilísticas como Miller-Rabin. A pesar de esto, el recíproco es una herramienta poderosa en demostraciones de teoría de números y problemas de olimpiada. Te permite deducir propiedades de $n$ basándote en la estructura del producto de los enteros que van antes de él.

La intuición detrás del recíproco depende de cómo se comportan los números compuestos. Si $n$ es compuesto, tiene divisores que están estrictamente entre $1$ y $n$. Estos divisores aparecen como factores en la expansión de $(n-1)!$, haciendo que el factorial comparta un factor común con $n$. Por lo tanto, para un $n$ compuesto, $(n-1)!$ suele ser congruente a $0 \pmod n$ (con la excepción específica de $n=4$), lo que hace imposible que el factorial sea congruente a $-1$.

Fórmulas Clave

El Recíproco de Wilson: Para un entero $n > 1$, $$ \text{Si } (n-1)! \equiv -1 \pmod n, \text{ entonces } n \text{ es primo.} $$

Teorema de Wilson (Forma Bicondicional): Si juntas el teorema y su recíproco, obtienes: $$ n \text{ es primo} \iff (n-1)! \equiv -1 \pmod n $$

Comportamiento de los Números Compuestos: Para un número compuesto $n$: $$ (n-1)! \equiv \begin{cases} 2 \pmod 4 & \text{si } n = 4 \ 0 \pmod n & \text{si } n \text{ es compuesto y } n > 4 \end{cases} $$

Demostración

Teorema: Si $n > 1$ es un entero tal que $(n-1)! \equiv -1 \pmod n$, entonces $n$ es primo.

Demostración: Vamos a demostrarlo por contradicción.

1. Supón que $(n-1)! \equiv -1 \pmod n$.
2. Supón, para llegar a una contradicción, que $n$ es compuesto.
3. Como $n$ es compuesto y $n > 1$, existe un divisor $d$ de $n$ tal que $1 < d < n$.
4. Como $d$ es un entero estrictamente menor que $n$, $d$ tiene que aparecer como uno de los factores en el producto de $(n-1)!$: $$ (n-1)! = 1 \times 2 \times \dots \times d \times \dots \times (n-1) $$
5. Entonces, $d$ divide a $(n-1)!$. En notación de aritmética modular: $$ (n-1)! \equiv 0 \pmod d $$
6. Por nuestra hipótesis inicial, tienes que $(n-1)! \equiv -1 \pmod n$. Esto significa que existe un entero $k$ tal que: $$ (n-1)! = kn - 1 $$
7. Como $d$ divide a $n$, sabes que $n \equiv 0 \pmod d$. Por lo tanto, $kn \equiv 0 \pmod d$.
8. Si sustituyes esto en la ecuación del paso 6 módulo $d$: $$ (n-1)! \equiv kn - 1 \equiv 0 - 1 \equiv -1 \pmod d $$
9. Ahora tienes dos afirmaciones contradictorias sobre $(n-1)! \pmod d$:
   • Del paso 5: $(n-1)! \equiv 0 \pmod d$
   • Del paso 8: $(n-1)! \equiv -1 \pmod d$
10. Esto implica que $0 \equiv -1 \pmod d$, o lo que es lo mismo, que $d$ divide a $1$.
11. Pero, como $d$ es un divisor de $n$ con $d > 1$, $d$ no puede dividir a $1$. ¡Ahí está la contradicción!

Por lo tanto, la suposición de que $n$ es compuesto tiene que ser falsa. $n$ tiene que ser primo. $\square$