Función de Euler $\varphi$

Motivación: ¿qué pasa cuando el módulo no es primo?

El Pequeño Teorema de Fermat funciona solo cuando el módulo es un número primo. Pero en la práctica, los problemas de olimpiada también presentan módulos compuestos: $a^n \pmod{100}$, $a^n \pmod{12}$, etc.

La generalización natural es el Teorema de Euler: si $\gcd(a, m) = 1$, entonces $a^{\varphi(m)} \equiv 1 \pmod m$, donde $\varphi(m)$ es la función de Euler (también llamada función indicatriz de Euler o función totiente).

Para $m = p$ primo, $\varphi(p) = p - 1$ y recuperamos Fermat. Pero $\varphi$ está definida para todo entero positivo, y dominar su cálculo abre la puerta a reducir exponentes módulo cualquier módulo.

Definición de $\varphi(n)$

Para un entero positivo $n$, $\varphi(n)$ es la cantidad de enteros en $\{1, 2, \ldots, n\}$ que son coprimos con $n$:

$\varphi(n) = \#\{k \in \{1, \ldots, n\} : \gcd(k, n) = 1\}$.

Ejemplos directos: $\varphi(1) = 1$ (el único entero en $\{1\}$ es $1$, y $\gcd(1,1)=1$). $\varphi(2) = 1$ (solo $1$). $\varphi(6) = 2$ (los coprimos con $6$ en $\{1,\ldots,6\}$ son $1$ y $5$). $\varphi(p) = p - 1$ para $p$ primo (todos los de $1$ a $p-1$ son coprimos con $p$).

Para calcular $\varphi(n)$ en general, la herramienta es la fórmula del producto.

Fórmula para potencias de primo y multiplicatividad

Para $p$ primo y $k \ge 1$: los enteros en $\{1, \ldots, p^k\}$ que no son coprimos con $p^k$ son exactamente los múltiplos de $p$: $p, 2p, 3p, \ldots, p^{k-1} \cdot p$. Hay $p^{k-1}$ tales múltiplos. Por lo tanto:

$\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$.

La función $\varphi$ es multiplicativa: si $\gcd(a, b) = 1$, entonces $\varphi(ab) = \varphi(a)\varphi(b)$. La demostración usa la correspondencia biyectiva entre el sistema reducido de residuos módulo $ab$ y el producto cartesiano de los sistemas reducidos módulo $a$ y módulo $b$ (por el Teorema Chino del Resto).

Combinando las dos propiedades: si $n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}$, entonces $\varphi(n) = \prod_{i=1}^{r} p_i^{a_i - 1}(p_i - 1) = n \prod_{p \mid n} (1 - 1/p)$.

Cálculo de $\varphi(n)$: ejemplos paso a paso

Ejemplo 1: $\varphi(12)$. Factorizamos $12 = 2^2 \cdot 3$. Entonces $\varphi(12) = \varphi(4) \cdot \varphi(3) = 2 \cdot 2 = 4$. Los coprimos con $12$ en $\{1,\ldots,12\}$ son $\{1, 5, 7, 11\}$. Correcto.

Ejemplo 2: $\varphi(100)$. $100 = 2^2 \cdot 5^2$. $\varphi(100) = \varphi(4)\varphi(25) = 2 \cdot 20 = 40$.

Ejemplo 3: $\varphi(p(p+1))$ para $p$ primo, $p$ impar. $p+1$ es par, $p$ es impar, $\gcd(p, p+1) = 1$. $\varphi(p(p+1)) = \varphi(p) \cdot \varphi(p+1) = (p-1)\varphi(p+1)$. El valor de $\varphi(p+1)$ depende de la factorización de $p+1$.

Propiedad importante: $\sum_{d \mid n} \varphi(d) = n$. Esta identidad es sorprendente: la suma de $\varphi(d)$ sobre todos los divisores $d$ de $n$ es exactamente $n$. Para $n = 6$: $\varphi(1)+\varphi(2)+\varphi(3)+\varphi(6) = 1+1+2+2 = 6$.

Teorema de Euler y aplicaciones

Con la función $\varphi$ definida, el Teorema de Euler afirma: si $\gcd(a, m) = 1$, entonces $a^{\varphi(m)} \equiv 1 \pmod m$.

La demostración es análoga a la del Pequeño Teorema de Fermat: se toma el sistema reducido de residuos módulo $m$ (que tiene $\varphi(m)$ elementos), se multiplica por $a$ (que lo permuta), y se comparan los productos de todos los elementos.

Aplicación: calcular $3^{2026} \pmod{100}$. Como $\gcd(3,100) = 1$ y $\varphi(100) = 40$, tenemos $3^{40} \equiv 1 \pmod{100}$. Ahora $2026 = 50 \cdot 40 + 26$, así $3^{2026} \equiv 3^{26} \pmod{100}$. Calculamos: $3^{10} = 59049 \equiv 49$, $3^{20} \equiv 49^2 = 2401 \equiv 1 \pmod{100}$. Entonces $3^{26} = 3^{20} \cdot 3^6 \equiv 1 \cdot 729 \equiv 29 \pmod{100}$.