Congruencias, clases de residuos, suma y multiplicación módulo n.
La aritmética modular es un sistema de aritmética para enteros donde los números "dan la vuelta" al llegar a cierto valor, que conocemos como el módulo. De forma técnica, decimos que dos enteros $a$ y $b$ son congruentes módulo $n$ (y lo escribimos como $a \equiv b \pmod n$) si su diferencia $a-b$ es divisible entre $n$. Esta relación divide al conjunto de todos los enteros en $n$ conjuntos distintos llamados "clases de residuos" o "clases de congruencia", que normalmente representamos con los residuos ${0, 1, 2, \dots, n-1}$. Para que te des una idea, esto se compara seguido con la "aritmética de reloj", donde sumarle 1 hora a las 12 da como resultado 1, no 13.
Esta herramienta es fundamental en la teoría de números porque te permite simplificar cálculos con números grandotes al enfocarte solo en los residuos. Es indispensable en las olimpiadas de matemáticas para encontrar las últimas cifras de potencias grandes, establecer reglas de divisibilidad y resolver ecuaciones diofánticas. Al transformar una igualdad sobre el conjunto infinito de los enteros en una congruencia sobre un conjunto finito de residuos, los problemas complejos de divisibilidad y estructura de los enteros se vuelven ejercicios de álgebra fáciles de manejar.
El poder de la aritmética modular está en que la congruencia es compatible con la suma, la resta y la multiplicación. Esto significa que puedes hacer estas operaciones con los números primero y luego sacar el residuo, o sacar los residuos primero y hacer las operaciones con ellos; el resultado módulo $n$ va a ser el mismo. Esta propiedad te permite reducir expresiones grandes paso a paso, manteniendo los números pequeños y fáciles de manejar durante todo el cálculo.
Definición de Congruencia $$a \equiv b \pmod n \iff n \mid (a-b) \iff a = kn + b \text{ para algún } k \in \mathbb{Z}$$ Esto es equivalente a decir que $a$ y $b$ tienen el mismo residuo cuando los divides entre $n$.
Propiedades Fundamentales Si $a \equiv b \pmod n$ y $c \equiv d \pmod n$, entonces:
Ley de Cancelación Ten en cuenta que la división no siempre es válida. Solo puedes cancelar un factor $c$ de ambos lados si $\gcd(c, n) = 1$: $$ac \equiv bc \pmod n \implies a \equiv b \pmod n \quad \text{solo si } \gcd(c, n) = 1$$ Si $\gcd(c, n) = g > 1$, entonces: $$ac \equiv bc \pmod n \implies a \equiv b \pmod{\frac{n}{g}}$$
Teorema: La aritmética modular preserva la suma y la multiplicación. Toma un entero positivo $n$. Si $a \equiv b \pmod n$ y $c \equiv d \pmod n$, entonces:
Demostración:
Por la definición de congruencia, $a \equiv b \pmod n$ implica que $n$ divide a $a-b$. Por lo tanto, puedes escribir: $$a = b + kn$$ para algún entero $k$.
De la misma forma, $c \equiv d \pmod n$ implica que $n$ divide a $c-d$. Así que puedes escribir: $$c = d + mn$$ para algún entero $m$.
Parte 1: Suma Checa la suma $a + c$ sustituyendo las expresiones que sacaste arriba: $$a + c = (b + kn) + (d + mn)$$ Acomoda los términos para agrupar los múltiplos de $n$: $$a + c = (b + d) + (kn + mn)$$ $$a + c = (b + d) + n(k + m)$$ Como $k$ y $m$ son enteros, $k+m$ también es un entero. Por definición, esto significa que: $$a + c \equiv b + d \pmod n$$
Parte 2: Multiplicación Ahora checa el producto $ac$ sustituyendo las expresiones de arriba: $$ac = (b + kn)(d + mn)$$ Desarrolla el producto usando la propiedad distributiva: $$ac = bd + b(mn) + (kn)d + (kn)(mn)$$ $$ac = bd + n(bm + kd + kmn)$$ Como $b, d, k, m$ son todos enteros, el término $(bm + kd + kmn)$ es un entero. Si pones $Z = bm + kd + kmn$, entonces: $$ac = bd + nZ$$ Esto implica que la diferencia $ac - bd$ es divisible entre $n$. Por lo tanto: $$ac \equiv bd \pmod n$$
$\square$