Enunciado del Teorema de Wilson

Teoría

El Teorema de Wilson es un resultado fundamental en la teoría de números que da una condición necesaria y suficiente para la primalidad basándose en aritmética modular. Específicamente, dice que un número natural $n > 1$ es un número primo si y solo si el producto de todos los enteros positivos menores que $n$ es congruente con $-1$ módulo $n$. Aunque el costo computacional de calcular factoriales hace que no sea eficiente para probar la primalidad de números grandes en la práctica, el teorema es una herramienta teórica muy poderosa que se usa seguido en las matemáticas de olimpiada para simplificar expresiones que tienen factoriales módulo $p$.

La intuición detrás del Teorema de Wilson se basa en el concepto de inversos multiplicativos modulares. En el conjunto de enteros ${1, 2, \dots, p-1}$, cada elemento $a$ tiene un único inverso multiplicativo $a^{-1}$ tal que $a \cdot a^{-1} \equiv 1 \pmod p$. Cuando calculas el factorial $(p-1)!$, multiplicas todos estos elementos entre sí. La mayoría de los elementos los puedes juntar en parejas con un inverso distinto, y su producto es congruente a $1$. Los únicos elementos que no puedes emparejar con un inverso distinto son los que son sus propios inversos (autoinversos).

Por lo tanto, el valor de $(p-1)! \pmod p$ lo determina totalmente el producto de estos elementos autoinversos. Algebraicamente, un elemento $x$ es su propio inverso si $x^2 \equiv 1 \pmod p$. Las soluciones a esta congruencia son $x \equiv 1$ y $x \equiv -1$ (que es $p-1$). Así que, cuando todos los demás elementos se cancelan para dar $1$, el producto se queda como $1 \cdot (p-1) \equiv -1 \pmod p$.

Fórmulas Clave

Teorema de Wilson Para cualquier número primo $p$: $$(p-1)! \equiv -1 \pmod p$$

Recíproco del Teorema de Wilson Para cualquier entero $n > 1$, si $(n-1)! \equiv -1 \pmod n$, entonces $n$ es primo.

Caso Compuesto A veces es útil saber cómo se comporta el factorial para los números compuestos. Para un número compuesto $n > 4$: $$(n-1)! \equiv 0 \pmod n$$ (Nota: Para $n=4$, $(4-1)! = 6 \equiv 2 \pmod 4$).

Demostración

Teorema: Si $p$ es un número primo, entonces $(p-1)! \equiv -1 \pmod p$.

Demostración: Considera el conjunto de enteros $S = {1, 2, \dots, p-1}$ bajo la multiplicación módulo $p$.

1. Existencia de inversos: Como $p$ es primo, para cada $a \in S$, $\gcd(a, p) = 1$. Por las propiedades de la aritmética modular (específicamente la Identidad de Bézout), la congruencia lineal $ax \equiv 1 \pmod p$ tiene una solución única para $x$ módulo $p$. Así, cada elemento en $S$ tiene un único inverso multiplicativo en $S$.

2. Identificando autoinversos: Hay que determinar qué elementos son sus propios inversos. Si un elemento $x$ es su propio inverso, entonces: $$x \cdot x \equiv 1 \pmod p$$ $$x^2 - 1 \equiv 0 \pmod p$$ $$(x-1)(x+1) \equiv 0 \pmod p$$

   Como $p$ es primo, puedes aplicar el Lema de Euclid: $p$ debe dividir a $(x-1)$ o $p$ debe dividir a $(x+1)$.

   • Si $p \mid (x-1)$, entonces $x \equiv 1 \pmod p$.
   • Si $p \mid (x+1)$, entonces $x \equiv -1 \equiv p-1 \pmod p$.

   Entonces, los únicos elementos en $S$ que son sus propios inversos son $1$ y $p-1$.

3. Emparejando elementos:

   • Caso 1: $p=2$. $(2-1)! = 1! = 1$. También $-1 \equiv 1 \pmod 2$. El teorema se cumple.
   • Caso 2: $p > 2$. El conjunto $S$ tiene $p-1$ elementos. Si quitas el $1$ y el $p-1$, quedan $p-3$ elementos. Como ninguno de estos elementos restantes es su propio inverso, los puedes agrupar en $\frac{p-3}{2}$ parejas distintas $(a, b)$ tales que $ab \equiv 1 \pmod p$.

4. Calculando el producto: Escribe el factorial $(p-1)!$ como el producto de todos los elementos en $S$: $$(p-1)! = 1 \cdot \left( \prod_{a \in S \setminus {1, p-1}} a \right) \cdot (p-1)$$

   Al agrupar los términos de en medio en sus parejas de inversos, el producto de esos términos es congruente a $1$: $$(p-1)! \equiv 1 \cdot (1)^{\frac{p-3}{2}} \cdot (p-1) \pmod p$$ $$(p-1)! \equiv p-1 \pmod p$$

   Como $p-1 \equiv -1 \pmod p$, concluyes que: $$(p-1)! \equiv -1 \pmod p$$

$\square$