El lenguaje de las congruencias

¿Por qué necesitamos un nuevo lenguaje?

Hasta ahora hemos trabajado con divisibilidad directa: "$m \mid n$" o "$m \nmid n$". Eso basta cuando queremos saber si un número divide exactamente. Pero muchos problemas de olimpiadas no preguntan si el cociente es exacto, sino qué residuo queda: ¿cuál es la última cifra de $7^{100}$? ¿Es $2^{50}+1$ divisible por $3$? Para responder estas preguntas eficientemente, Gauss inventó la notación de congruencias.

La idea es sencilla: dos enteros $a$ y $b$ se comportan igual módulo $m$ si dejan el mismo residuo al dividir por $m$. En lugar de decir "el residuo de $a$ al dividir por $m$ es igual al residuo de $b$ al dividir por $m$", escribimos la congruencia $a \equiv b \pmod{m}$.

Esta notación no es solo abreviatura: tiene su propia aritmética, sus propios teoremas, y hace transparentes patrones que de otra manera serían invisibles.

Definición formal y ejemplos

Sea $m$ un entero positivo llamado el módulo. Decimos que $a$ es **congruente a $b$ módulo $m$**, y escribimos $a \equiv b \pmod{m}$, si $m \mid (a - b)$, es decir, si existe un entero $k$ tal que $a - b = km$.

Ejemplos: $17 \equiv 2 \pmod{5}$ porque $17 - 2 = 15 = 3 \cdot 5$. También $-3 \equiv 4 \pmod{7}$ porque $-3 - 4 = -7 = (-1) \cdot 7$. Nota que los negativos funcionan perfectamente; el residuo de $-3$ módulo $7$ es $4$ (y no $-3$), porque siempre elegimos el residuo en $\{0, 1, \ldots, m-1\}$.

Casos especiales que ya conoces sin saberlo: $a \equiv 0 \pmod{m}$ es exactamente $m \mid a$. La paridad ($a$ par o impar) es $a \equiv 0 \pmod{2}$ o $a \equiv 1 \pmod{2}$. Las divisibilidades por $3$, $9$ y $11$ que aprendiste en primaria son congruencias disfrazadas.

La congruencia como relación de equivalencia

Fijado el módulo $m$, la relación "ser congruente módulo $m$" es una relación de equivalencia: es reflexiva ($a \equiv a$), simétrica ($a \equiv b \Rightarrow b \equiv a$) y transitiva ($a \equiv b$ y $b \equiv c \Rightarrow a \equiv c$). Cada una de estas propiedades se verifica directamente desde la definición.

Esto quiere decir que los enteros se agrupan en clases de equivalencia: la clase de $r$ módulo $m$ es el conjunto $\{\ldots, r-2m, r-m, r, r+m, r+2m, \ldots\}$. Como $r$ puede ser cualquier entero entre $0$ y $m-1$, hay exactamente $m$ clases. A este conjunto de clases se le llama $\mathbb{Z}/m\mathbb{Z}$ o $\mathbb{Z}_m$.

Pensar en clases de residuos aclara la aritmética modular: operar con congruencias es operar con estas clases. Cuando sumamos $5 + 8$ módulo $7$, en realidad estamos sumando la clase de $5$ con la clase de $8$ y obtenemos la clase de $13 \equiv 6 \pmod 7$.

Criterios de divisibilidad como congruencias

La representación decimal de un número $n = d_k \cdot 10^k + \cdots + d_1 \cdot 10 + d_0$ permite deducir criterios de divisibilidad usando que $10 \equiv 1 \pmod{9}$ y $10 \equiv -1 \pmod{11}$.

Para el $9$: como $10^j \equiv 1^j = 1 \pmod 9$ para todo $j \ge 0$, se tiene $n \equiv d_k + \cdots + d_1 + d_0 \pmod 9$. Entonces $9 \mid n$ si y solo si $9$ divide a la suma de sus dígitos.

Para el $11$: como $10 \equiv -1 \pmod{11}$, entonces $10^j \equiv (-1)^j \pmod{11}$, y $n \equiv d_0 - d_1 + d_2 - \cdots \pmod{11}$. Es decir, $11 \mid n$ si y solo si $11$ divide a la suma alternada de dígitos (de menor a mayor posición). Estos criterios, que aprendiste de memoria, ahora tienen una demostración de dos líneas.

Residuos mínimos no negativos y notación práctica

Por convenio, cuando decimos "el residuo de $a$ módulo $m$", nos referimos al único entero $r$ con $0 \le r < m$ tal que $a \equiv r \pmod m$. Este $r$ existe y es único por el algoritmo de la división. Algunas veces es cómodo usar residuos centrados en el rango $\{-(m-1)/2, \ldots, (m-1)/2\}$ para $m$ impar, eligiendo el representante de menor valor absoluto.

En olimpiadas se escribe indistintamente $a \pmod m$ (el residuo) o $a \equiv b \pmod m$ (la congruencia). Aprende a leer el contexto: si dice "calcula $2^{100} \pmod 7$" pide un número; si dice "demuestra que $a \equiv b \pmod m$" pide una demostración.