Teoremas de Euler y Wilson

Más allá de los primos: el Teorema de Euler

El Pequeño Teorema de Fermat requiere que el módulo sea primo. ¿Qué ocurre si el módulo es compuesto? Euler generalizó el resultado: si $\gcd(a, n) = 1$, entonces $a^{\varphi(n)} \equiv 1 \pmod{n}$, donde $\varphi(n)$ es la función de Euler (o función totient), que cuenta los enteros en $\{1, \ldots, n\}$ coprimos con $n$.

La demostración sigue exactamente la misma idea que el PTF: se considera el conjunto $S$ de los enteros en $\{1, \ldots, n\}$ coprimos con $n$ (hay $\varphi(n)$ de ellos), y se muestra que la función $f(x) = ax \bmod n$ es una biyección de $S$ en $S$ cuando $\gcd(a,n)=1$. El argumento del producto da entonces $a^{\varphi(n)} \equiv 1 \pmod{n}$.

Cuando $n = p$ es primo, $\varphi(p) = p - 1$ (todos los enteros de $1$ a $p-1$ son coprimos con $p$), y el Teorema de Euler se reduce al PTF. El Teorema de Euler es, pues, una generalización que nos da herramientas para trabajar con cualquier módulo, no solo primos.

La función $\varphi$ de Euler: fórmula y cálculo

Para aplicar el Teorema de Euler necesitamos calcular $\varphi(n)$. Las fórmulas clave son:

Primo: $\varphi(p) = p - 1$.

Potencia de primo: $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$. Razonamiento: los enteros en $\{1, \ldots, p^k\}$ no coprimos con $p^k$ son exactamente los múltiplos de $p$, que son $p, 2p, \ldots, p^{k-1} \cdot p$; hay $p^{k-1}$ de ellos.

Multiplicatividad: Si $\gcd(m, n) = 1$, entonces $\varphi(mn) = \varphi(m)\varphi(n)$.

Combinando: si $n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$, entonces $\varphi(n) = n \prod_{p \mid n} \left(1 - \tfrac{1}{p}\right) = p_1^{a_1-1}(p_1-1) \cdots p_r^{a_r-1}(p_r-1)$.

Ejemplo: $\varphi(60) = \varphi(4 \cdot 3 \cdot 5) = \varphi(4)\varphi(3)\varphi(5) = 2 \cdot 2 \cdot 4 = 16$. Es decir, hay exactamente $16$ enteros en $\{1, \ldots, 60\}$ coprimos con $60$.

Euler en acción: potencias módulo compuesto

Calcula $7^{100} \bmod 36$. Tenemos $36 = 4 \cdot 9$, $\gcd(7, 36) = 1$. Calculamos $\varphi(36) = \varphi(4)\varphi(9) = 2 \cdot 6 = 12$. Por Euler, $7^{12} \equiv 1 \pmod{36}$.

Reducimos el exponente: $100 = 8 \cdot 12 + 4$, así $7^{100} \equiv 7^4 \pmod{36}$. Calculamos: $7^2 = 49 \equiv 13 \pmod{36}$; $7^4 = 13^2 = 169 = 4 \cdot 36 + 25 \equiv 25 \pmod{36}$.

Respuesta: $7^{100} \equiv 25 \pmod{36}$.

Atención: el Teorema de Euler dice que $\varphi(n)$ es un exponente que funciona, pero no necesariamente el mínimo. El mínimo exponente $k$ tal que $a^k \equiv 1 \pmod{n}$ se llama el orden de $a$ módulo $n$, y siempre divide a $\varphi(n)$. En la lección 3.1 profundizaremos en este concepto.

Teorema de Wilson: los primos y el factorial

El Teorema de Wilson enuncia: $p$ es primo si y solo si $(p-1)! \equiv -1 \pmod{p}$.

La dirección "solo si" ($p$ primo $\Rightarrow$ $(p-1)! \equiv -1$) es la más importante y la demostramos aquí. La idea es emparejar cada $a \in \{1, \ldots, p-1\}$ con su inverso multiplicativo módulo $p$.

En $\mathbb{Z}/p\mathbb{Z}$, cada elemento $a$ tiene un único inverso $a^{-1}$ tal que $a \cdot a^{-1} \equiv 1 \pmod{p}$. El inverso de $a$ coincide con $a$ (es decir, $a$ es su propio inverso) si y solo si $a^2 \equiv 1 \pmod{p}$, lo que equivale a $p \mid (a-1)(a+1)$, es decir $a \equiv 1$ o $a \equiv -1 \equiv p-1 \pmod{p}$. Así, los únicos "puntos fijos" de la inversión en $\{1, \ldots, p-1\}$ son $1$ y $p-1$.

Los demás elementos se emparejan en pares $\{a, a^{-1}\}$ con $a \ne a^{-1}$. Al calcular el producto $(p-1)! = 1 \cdot 2 \cdots (p-1)$, todos los pares contribuyen $a \cdot a^{-1} = 1$, y sobran $1$ y $p-1$. Por lo tanto $(p-1)! \equiv 1 \cdot (p-1) \equiv -1 \pmod{p}$.

Wilson: aplicaciones en olimpiadas

Una aplicación directa: calcular $(p-1)! \bmod p^2$. Para $p = 5$: $(5-1)! = 24 \equiv 24 - 0 \cdot 25 = 24 \pmod{25}$, y efectivamente $24 \equiv -1 \pmod{25}$. Para $p = 7$: $6! = 720 = 28 \cdot 25 + 20$... mejor con módulo $49$: $720 = 14 \cdot 49 + 34$, así $6! \equiv 34 \equiv -15 \pmod{49}$. Este patrón lleva a una generalización de Wilson para $p^2$, pero eso pertenece a la teoría más avanzada.

Otra aplicación: demostrar que si $p$ es primo impar y $p \equiv 1 \pmod{4}$, entonces existe un entero $x$ tal que $x^2 \equiv -1 \pmod{p}$. Por Wilson, $((p-1)/2)!^2 \equiv (-1)^{(p-1)/2}(p-1)! \equiv (-1)^{(p-1)/2} \cdot (-1) \pmod{p}$. Si $p \equiv 1 \pmod 4$, $(p-1)/2$ es par, luego $(-1)^{(p-1)/2}=1$ y $x = ((p-1)/2)!$ satisface $x^2 \equiv -1 \pmod p$.

Wilson también puede aparecer en problemas del tipo "muestra que $p^2 \mid (p-1)!+(p+1)!+1$": con un poco de álgebra y Wilson, estas expresiones se simplifican rápidamente. La clave es siempre reconocer el patrón $(p-1)! \equiv -1$.

Diferencias entre Euler y Wilson en la práctica

El Teorema de Euler reduce exponentes cuando la base y el módulo son coprimos: $a^k \equiv a^{k \bmod \varphi(n)} \pmod{n}$. Es la herramienta de cálculo por excelencia.

El Teorema de Wilson actúa sobre factoriales y es la caracterización aritmética de los primos. En competencias aparece cuando la expresión contiene $k!$ o productos de enteros consecutivos, o cuando hay que probar algo sobre $(p-1)!$.

Ambos teoremas se complementan con el PTF: el PTF es el caso especial $n=p$ de Euler. Cuando el módulo es primo, usa PTF (más simple). Cuando es compuesto, calcula $\varphi(n)$ y aplica Euler. Cuando hay factoriales, piensa en Wilson.