Aritmética Modular

Teoría

La aritmética modular, a la que seguido le dicen "aritmética de reloj", es un sistema de aritmética para enteros donde los números "dan la vuelta" después de llegar a cierto valor, llamado el módulo. De forma técnica, decimos que dos enteros $a$ y $b$ son congruentes módulo $n$ (lo escribimos como $a \equiv b \pmod n$) si su diferencia $a - b$ es un múltiplo entero de $n$. Dicho de otra forma, $a$ y $b$ dejan el mismo residuo cuando los divides entre $n$. Este concepto divide al conjunto infinito de los enteros en $n$ clases de equivalencia distintas (clases de residuos), transformando problemas con infinitas posibilidades en estructuras finitas.

Este sistema es fundamental en la teoría de números porque las congruencias respetan las operaciones de suma, resta y multiplicación. Si $a \equiv b \pmod n$ y $c \equiv d \pmod n$, entonces $a+c \equiv b+d \pmod n$ y $ac \equiv bd \pmod n$. Esto te permite simplificar expresiones complejas, determinar la divisibilidad, encontrar los últimos dígitos de potencias grandes y resolver ecuaciones diofánticas analizándolas sobre un módulo finito. Es la columna vertebral de la criptografía moderna (como RSA) y aparece en todos lados en las competencias, desde el AMC 10 hasta la IMO.

La intuición clave en la aritmética modular es que puedes descartar múltiplos de $n$ en cualquier paso de un cálculo sin afectar el resultado final módulo $n$. Sin embargo, hay que tener cuidado con la división: no puedes simplemente dividir ambos lados de una congruencia por un factor común a menos que ese factor sea coprimo con el módulo. Esto te lleva al concepto de inversos modulares y al estudio del grupo multiplicativo de enteros módulo $n$, lo que da lugar a teoremas centrales de Fermat, Euler y Wilson.

Fórmulas Clave

Propiedades Básicas de las Congruencias Para enteros $a, b, c, d$ y un módulo $n > 1$: $$a \equiv b \pmod n \iff n \mid (a-b)$$ $$a \equiv b \pmod n \implies a^k \equiv b^k \pmod n \quad \text{para enteros } k \ge 1$$

Inversos Modulares Un entero $a$ tiene un inverso multiplicativo módulo $n$ (que escribimos como $a^{-1}$) si y solo si $\gcd(a, n) = 1$. Si existe: $$a \cdot a^{-1} \equiv 1 \pmod n$$

Función Totiente de Euler $\phi(n)$ Cuenta la cantidad de enteros positivos menores o iguales a $n$ que son primos relativos con $n$. Si $n = p_1^{e_1} \cdots p_k^{e_k}$: $$\phi(n) = n \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)$$

Teorema de Euler Si $\gcd(a, n) = 1$, entonces: $$a^{\phi(n)} \equiv 1 \pmod n$$

Pequeño Teorema de Fermat Un caso especial del Teorema de Euler donde el módulo es un primo $p$. Si $p$ es primo: $$a^p \equiv a \pmod p$$ Si $p \nmid a$, entonces: $$a^{p-1} \equiv 1 \pmod p$$

Teorema de Wilson Para un entero $p > 1$, $p$ es primo si y solo si: $$(p-1)! \equiv -1 \pmod p$$

Teorema del Residuo Chino (TRC) Si $n_1, n_2, \dots, n_k$ son coprimos dos a dos, entonces el sistema de congruencias $x \equiv a_i \pmod{n_i}$ tiene una solución única módulo $N = n_1 n_2 \dots n_k$.

Demostración

Teorema: Teorema de Euler Sea $n$ un entero positivo y $a$ un entero tal que $\gcd(a, n) = 1$. Entonces $a^{\phi(n)} \equiv 1 \pmod n$.

Demostración: Toma $R = {r_1, r_2, \dots, r_{\phi(n)}}$ como el conjunto de enteros positivos menores que $n$ que son coprimos con $n$. A este conjunto se le conoce como un sistema reducido de residuos módulo $n$. Por la definición de la función totiente de Euler, hay exactamente $\phi(n)$ de estos elementos.

Considera el conjunto $S$ formado al multiplicar cada elemento de $R$ por $a$: $$S = {ar_1, ar_2, \dots, ar_{\phi(n)}}$$

Paso 1: Los elementos de $S$ son coprimos con $n$. Como $\gcd(a, n) = 1$ y $\gcd(r_i, n) = 1$ para toda $i$, el producto $ar_i$ también tiene que ser coprimo con $n$. Así, cada elemento en $S$ es congruente a algún elemento de un sistema reducido de residuos.

Paso 2: Los elementos de $S$ son distintos módulo $n$. Supón que $ar_i \equiv ar_j \pmod n$ para algunos índices $i$ y $j$. Como $\gcd(a, n) = 1$, $a$ tiene un inverso modular $a^{-1}$. Si multiplicas ambos lados por $a^{-1}$, obtienes: $$a^{-1}(ar_i) \equiv a^{-1}(ar_j) \pmod n \implies r_i \equiv r_j \pmod n$$ Como $r_i$ y $r_j$ son elementos distintos del conjunto $R$ (donde todos los elementos son diferentes y menores que $n$), forzosamente $i = j$. Por lo tanto, todos los elementos de $S$ son distintos módulo $n$.

Paso 3: Comparando los productos. Como el conjunto $S$ tiene $\phi(n)$ enteros que son distintos módulo $n$ y todos son coprimos con $n$, los elementos de $S$ tienen que ser una permutación de los elementos de $R$ módulo $n$. Por lo tanto, el producto de los elementos en $S$ es congruente al producto de los elementos en $R$: $$\prod_{i=1}^{\phi(n)} (ar_i) \equiv \prod_{i=1}^{\phi(n)} r_i \pmod n$$

Puedes factorizar $a$ de cada término del lado izquierdo. Hay $\phi(n)$ términos, así que obtienes $a^{\phi(n)}$: $$a^{\phi(n)} \cdot \left(\prod_{i=1}^{\phi(n)} r_i\right) \equiv \prod$$