Resolver congruencias lineales ax ≡ b (mod n) paso a paso

La idea

Una congruencia lineal es una ecuación

$$a\,x\equiv b\pmod{n}.$$

Se busca el entero $x$ (módulo $n$) tal que $a\,x-b$ sea múltiplo de $n$. Sea $d=\operatorname{mcd}(a,n)$:

• si $d\nmid b$, no hay solución;
• si $d\mid b$, hay $d$ soluciones módulo $n$.

Cómo se resuelve

1. Calcular $d=\operatorname{mcd}(a,n)$ y comprobar que divide a $b$.
2. Dividir todo, también el módulo, entre $d$: $a'x\equiv b'\pmod{n'}$, con $\operatorname{mcd}(a',n')=1$.
3. Multiplicar por el inverso $a'^{-1}$ módulo $n'$: $x\equiv a'^{-1}b'\pmod{n'}$.
4. Las $d$ soluciones módulo $n$ son $x_0,\ x_0+n',\ x_0+2n',\dots$

Un ejemplo completo

Resolvamos $9x\equiv12\pmod{21}$.

1. $d=\operatorname{mcd}(9,21)=3$, y $3\mid12$: hay $3$ soluciones.
2. Dividimos entre $3$: $3x\equiv4\pmod{7}$.
3. El inverso de $3$ módulo $7$ es $5$, pues $3\cdot5=15\equiv1$. Entonces

$$x\equiv5\cdot4=20\equiv6\pmod{7}.$$

4. Módulo $21$ las soluciones son

$$x\equiv6,\ 13,\ 20\pmod{21}.$$

Comprobación: $9\cdot6=54=2\cdot21+12$, $9\cdot13=117=5\cdot21+12$ y $9\cdot20=180=8\cdot21+12$.

Errores típicos

• Dividir entre $d$ solo en $a$ y $b$ y olvidarse del módulo.
• Dar una sola solución cuando $d>1$: hay $d$ soluciones módulo $n$.
• Dividir entre $a$ sin más cuando $a$ no tiene inverso: primero hay que simplificar.
• No comprobar que $d\mid b$ antes de empezar.

Dónde se usa

Aparece al descifrar el cifrado afín, al recuperar una cifra borrosa de un ISBN-10 (es una congruencia módulo 11) y como paso previo para resolver sistemas con el teorema chino del resto.