Propiedades y operaciones

Suma, resta y multiplicación son compatibles

Sean $a \equiv b \pmod m$ y $c \equiv d \pmod m$. Las tres operaciones básicas respetan las congruencias: $a + c \equiv b + d \pmod m$, $a - c \equiv b - d \pmod m$, y $a \cdot c \equiv b \cdot d \pmod m$.

La demostración es directa: si $m \mid (a-b)$ y $m \mid (c-d)$, entonces $m \mid (a+c)-(b+d)$ y $m \mid (a-c)-(b-d)$. Para el producto: $ac - bd = ac - bc + bc - bd = c(a-b) + b(c-d)$, y como $m$ divide a cada sumando, $m \mid ac - bd$.

Consecuencia práctica: para calcular un residuo, puedes reducir cada operando a su residuo módulo $m$ antes de operar. Esto evita trabajar con números enormes.

Potencias: el truco de reducción iterativa

La compatibilidad con la multiplicación se extiende a potencias: si $a \equiv b \pmod m$, entonces $a^n \equiv b^n \pmod m$ para todo entero $n \ge 0$. Basta aplicar la regla del producto $n$ veces.

Para calcular $a^n \pmod m$ de forma eficiente, se usa la exponenciación rápida: se expresa $n$ en binario y se van elevando al cuadrado los residuos parciales, reduciendo módulo $m$ en cada paso. Así se calculan potencias como $7^{200} \pmod{13}$ en unos pocos pasos en lugar de calcular $7^{200}$ directamente.

Ejemplo: calcular $3^{10} \pmod 7$. Primero: $3^1 \equiv 3$, $3^2 \equiv 2$, $3^4 \equiv 4$, $3^8 \equiv 2 \pmod 7$. Luego $3^{10} = 3^8 \cdot 3^2 \equiv 2 \cdot 2 = 4 \pmod 7$.

Cancelación: cuándo se puede y cuándo no

En aritmética ordinaria, si $ac = bc$ y $c \ne 0$ entonces $a = b$. Con congruencias hay que tener cuidado: de $ac \equiv bc \pmod m$ no se concluye $a \equiv b \pmod m$ en general. Por ejemplo, $2 \cdot 3 \equiv 2 \cdot 6 \pmod 6$ (ambos son $6 \equiv 0$), pero $3 \not\equiv 6 \pmod 6$.

La regla correcta de cancelación es: $ac \equiv bc \pmod m \iff a \equiv b \pmod{m / \gcd(c, m)}$. En particular, si $\gcd(c, m) = 1$ (es decir, $c$ y $m$ son coprimos), entonces sí se puede cancelar $c$ directamente: $ac \equiv bc \pmod m \implies a \equiv b \pmod m$.

Esto motiva el concepto de inverso modular: cuando $\gcd(c, m) = 1$, existe un entero $c^{-1}$ tal que $c \cdot c^{-1} \equiv 1 \pmod m$. Multiplicar por $c^{-1}$ es la forma rigurosa de "dividir" en aritmética modular.

Combinando congruencias con módulos distintos

A veces sabemos que $a \equiv r_1 \pmod{m_1}$ y $a \equiv r_2 \pmod{m_2}$ y queremos una congruencia módulo $m_1 m_2$. Esto solo funciona sin problemas cuando $\gcd(m_1, m_2) = 1$: en ese caso el Teorema Chino del Resto (que estudiarás en niveles superiores) garantiza una solución única módulo $m_1 m_2$.

Para módulos no coprimos hay que verificar una condición de compatibilidad: el sistema $a \equiv r_1 \pmod{m_1}$, $a \equiv r_2 \pmod{m_2}$ tiene solución si y solo si $\gcd(m_1, m_2) \mid (r_1 - r_2)$. En olimpiadas de nivel 1, basta entender el caso coprimo.