Congruencia (Modular)
Dos enteros son congruentes módulo n si tienen el mismo residuo al dividirse entre n, escrito a ≡ b (mod n).
Formula
a \equiv b \pmod{n} \text{ iff } n \mid (a - b)
Definition
Dos números son congruentes módulo $n$ si tienen el mismo residuo al dividirse entre $n$; el símbolo $\equiv$ significa "congruente," y $\pmod{n}$ indica el módulo. Formalmente, $a \equiv b \pmod{n}$ si $n \mid (a - b)$; la congruencia es una relación de equivalencia (reflexiva, simétrica, transitiva) que se preserva bajo la suma y la multiplicación, así que $a \equiv b$ y $c \equiv d \pmod{n}$ implica $a+c \equiv b+d$ y $ac \equiv bd \pmod{n}$. La congruencia módulo $n$ divide $\mathbb{Z}$ en $n$ clases residuales, formando el anillo cociente $\mathbb{Z}/n\mathbb{Z}$; el Teorema Chino del Resto da una solución única módulo $n_1 \times \ldots \times n_k$ a un sistema de congruencias con módulos coprimos por pares, y el teorema de Euler establece que $a^{\phi(n)} \equiv 1 \pmod{n}$ cuando $\gcd(a,n) = 1$.
Example
$17 \equiv 2 \pmod{5}$ porque ambos tienen residuo $2$ al dividirse entre $5$, y de hecho $17 - 2 = 15$ es divisible entre $5$. Resolviendo $3x \equiv 6 \pmod{9}$: dividiendo entre $\gcd(3,9)=3$ (que divide a $6$) se obtiene $x \equiv 2 \pmod{3}$, con soluciones $2, 5, 8, \ldots$; las congruencias lineales $ax \equiv b \pmod{n}$ tienen soluciones si y solo si $\gcd(a,n) \mid b$. El Pequeño Teorema de Fermat permite calcular $2^{100} \bmod 7$ eficientemente: como $2^6 \equiv 1 \pmod 7$, $2^{100} = (2^6)^{16} \times 2^4 \equiv 16 \equiv 2 \pmod{7}$, usando exponenciación modular por elevación al cuadrado repetida.
Key Insight
La congruencia agrupa números en familias: todos los números congruentes mod 12 "marcan la misma hora en un reloj," y cuando sí tiene soluciones, una congruencia lineal tiene exactamente $\gcd(a,n)$ soluciones módulo $n$. La aritmética modular módulo potencias de primos proporciona los enteros p-ádicos $\mathbb{Z}_p$, una completación de $\mathbb{Z}$ análoga a $\mathbb{R}$ como completación de $\mathbb{Q}$, con el análisis p-ádico como un rico paralelo al análisis real en la teoría de números.