El lenguaje de las congruencias

El dígito final como motivación

Antes de cualquier definición, mira este problema: ¿cuál es el dígito de las unidades de $7^{100}$? Una calculadora desborda. La fuerza bruta es impráctica. Sin embargo, la respuesta —que es $1$— se obtiene en tres líneas si tienes el lenguaje correcto.

La observación clave es que el dígito de las unidades de un producto solo depende de los dígitos de las unidades de los factores. Diez veces siete da setenta: el dígito es cero. Siete veces siete da cuarenta y nueve: el dígito es nueve. Esta "aritmética del resto" es exactamente lo que formalizamos con las congruencias.

La idea de trabajar con restos módulo $n$ organiza los enteros en clases según su resto al dividir por $n$, y permite reemplazar números grandes por sus representantes pequeños en cada clase. Todo el poder de la aritmética modular descansa en ese principio.

Definición y notación

Sea $n$ un entero positivo. Decimos que $a$ es **congruente con $b$ módulo $n$**, y escribimos $a \equiv b \pmod{n}$, si $n \mid a - b$, es decir, si $a$ y $b$ dejan el mismo resto al dividir por $n$.

Equivalentemente, $a \equiv b \pmod{n}$ si y solo si existen un entero $k$ tal que $a = b + kn$. La cantidad $n$ se llama el módulo. Cuando $n$ está claro del contexto, escribimos simplemente $a \equiv b$.

Ejemplos inmediatos: $17 \equiv 2 \pmod{5}$ porque $17 - 2 = 15 = 3 \cdot 5$. También $-3 \equiv 7 \pmod{5}$ porque $-3 - 7 = -10 = -2 \cdot 5$. Observa que los negativos se tratan igual que los positivos: la congruencia es una relación de equivalencia.

La clase de equivalencia de $a$ módulo $n$ es el conjunto $\{\ldots, a-n,\, a,\, a+n,\, a+2n, \ldots\}$. El representante canónico es el resto al dividir por $n$, que está en $\{0, 1, \ldots, n-1\}$. El conjunto de clases de equivalencia se denota $\mathbb{Z}/n\mathbb{Z}$.

Propiedades fundamentales

La congruencia se comporta perfectamente con la suma y el producto. Si $a \equiv b \pmod{n}$ y $c \equiv d \pmod{n}$, entonces:

Suma: $a + c \equiv b + d \pmod{n}$. Demostración: $(a+c) - (b+d) = (a-b) + (c-d)$. Ambos sumandos son múltiplos de $n$, luego su suma también lo es.

Multiplicación: $a \cdot c \equiv b \cdot d \pmod{n}$. Demostración: $ac - bd = a(c-d) + d(a-b)$. El primer término es múltiplo de $n$ porque $n \mid c-d$; el segundo porque $n \mid a-b$.

Potencias: Si $a \equiv b \pmod{n}$, entonces $a^k \equiv b^k \pmod{n}$ para todo $k \ge 0$. Esto se deduce de la multiplicación por inducción: $a^k = a \cdot a^{k-1} \equiv b \cdot b^{k-1} = b^k$.

Una advertencia importante: la división no siempre es válida. De $ac \equiv bc \pmod{n}$ no se concluye $a \equiv b \pmod{n}$ en general. Solo podemos cancelar $c$ si $\gcd(c, n) = 1$; en ese caso obtenemos $a \equiv b \pmod{n}$.

Potencias cíclicas y clases de residuos

Las propiedades anteriores hacen que las potencias de un entero módulo $n$ sean periódicas. Para calcular $a^k \bmod n$ basta rastrear la sucesión $a^1, a^2, a^3, \ldots$ hasta que se repita. Por el principio de casillas, esta sucesión es eventualmente periódica, y para $\gcd(a,n)=1$ es puramente periódica desde el principio.

El truco práctico es reducir la base primero: reemplaza $a$ por su resto módulo $n$ antes de elevar. Esto mantiene todos los números pequeños y evita aritmética con enteros gigantes.

Ejemplo: calcula $7^{100} \bmod 10$. Reducimos mod 10 y observamos la sucesión de potencias de $7$: $7^1 \equiv 7$, $7^2 \equiv 9$, $7^3 \equiv 3$, $7^4 \equiv 1 \pmod{10}$. El ciclo tiene período 4. Como $100 = 4 \cdot 25$, concluimos $7^{100} \equiv (7^4)^{25} \equiv 1^{25} \equiv 1 \pmod{10}$.

Ejemplo trabajado: últimas dos cifras de $7^{100}$

Ahora buscamos $7^{100} \bmod 100$, es decir, las últimas dos cifras decimales. La estrategia es la misma: rastrear la sucesión de potencias de $7$ módulo $100$.

Calculamos: $7^1 = 7$; $7^2 = 49$; $7^4 = 49^2 = 2401 \equiv 1 \pmod{100}$. Comprobemos: $2401 - 1 = 2400 = 24 \cdot 100$. Correcto.

Como $7^4 \equiv 1 \pmod{100}$ y $100 = 4 \cdot 25$, obtenemos $7^{100} = (7^4)^{25} \equiv 1^{25} = 1 \pmod{100}$.

Conclusión: las últimas dos cifras de $7^{100}$ son $\mathbf{01}$. Eso incluye el dígito de las unidades (que ya sabíamos que era 1) y nos da además que la decena es cero. Este tipo de cálculo —antes aparentemente imposible— se convierte en rutina con congruencias.

Congruencias en problemas olímpicos

Las congruencias no solo sirven para calcular dígitos: son una herramienta de demostración. Para probar que una expresión no puede ser un cuadrado perfecto, basta encontrar un módulo $n$ tal que la expresión tome un valor que no es residuo cuadrático módulo $n$. Para probar divisibilidad, se trabaja directamente con la congruencia.

Un ejemplo típico: demostrar que $n^2 + n + 1$ nunca es divisible por $5$ para ningún entero $n$. Basta verificar los $5$ posibles restos de $n$ módulo $5$: para $n \equiv 0, 1, 2, 3, 4$, los valores de $n^2 + n + 1$ son $1, 3, 7 \equiv 2, 13 \equiv 3, 21 \equiv 1 \pmod{5}$ respectivamente. Ninguno es $0$. Listo.

Este método —evaluar en todos los restos posibles— es sistemático y no requiere ningún insight especial. En olimpiadas se llama a veces "análisis de casos módulo $n$", y es uno de los primeros movimientos que deberías intentar cuando ves un problema de divisibilidad.