Ecuación de congruencia lineal

Esta ecuación es de la forma:

$$a \cdot x \equiv b \pmod n,$$

donde $a$, $b$ y $n$ son enteros dados y $x$ es un entero desconocido.

Se requiere hallar el valor $x$ del intervalo $[0, n-1]$ (claramente, en toda la recta numérica puede haber infinitas soluciones que diferirán entre sí en $n \cdot k$, donde $k$ es cualquier entero). Si la solución no es única, entonces consideraremos cómo obtener todas las soluciones.

Solución hallando el elemento inverso

Consideremos primero un caso más simple en el que $a$ y $n$ son coprimos ($\gcd(a, n) = 1$). Entonces se puede hallar el inverso de $a$, y multiplicando ambos lados de la ecuación por el inverso, podemos obtener una solución única.

$$x \equiv b \cdot a ^ {- 1} \pmod n$$

Ahora consideremos el caso en que $a$ y $n$ no son coprimos ($\gcd(a, n) \ne 1$). Entonces la solución no siempre existirá (por ejemplo $2 \cdot x \equiv 1 \pmod 4$ no tiene solución).

Sea $g = \gcd(a, n)$, es decir, el máximo común divisor de $a$ y $n$ (que en este caso es mayor que uno).

Entonces, si $b$ no es divisible por $g$, no hay solución. De hecho, para cualquier $x$ el lado izquierdo de la ecuación $a \cdot x \pmod n$ siempre es divisible por $g$, mientras que el lado derecho no es divisible por él, de lo que se sigue que no hay soluciones.

Si $g$ divide a $b$, entonces al dividir ambos lados de la ecuación por $g$ (es decir, dividir $a$, $b$ y $n$ por $g$), obtenemos una nueva ecuación:

$$a^\prime \cdot x \equiv b^\prime \pmod{n^\prime}$$

en la que $a^\prime$ y $n^\prime$ ya son coprimos, y ya aprendimos a tratar una ecuación de ese tipo. Obtenemos $x^\prime$ como solución para $x$.

Está claro que este $x^\prime$ también será una solución de la ecuación original. Sin embargo no será la única solución. Se puede mostrar que la ecuación original tiene exactamente $g$ soluciones, y se verán así:

$$x_i \equiv (x^\prime + i\cdot n^\prime) \pmod n \quad \text{for } i = 0 \ldots g-1$$

Resumiendo, podemos decir que la cantidad de soluciones de la ecuación de congruencia lineal es igual o bien a $g = \gcd(a, n)$ o bien a cero.

Solución con el Algoritmo de Euclides extendido

Podemos reescribir la congruencia lineal como la siguiente ecuación diofántica:

$$a \cdot x + n \cdot k = b,$$

donde $x$ y $k$ son enteros desconocidos.

El método para resolver esta ecuación se describe en el artículo correspondiente Ecuaciones diofánticas lineales y consiste en aplicar el Algoritmo de Euclides extendido.

También describe el método para obtener todas las soluciones de esta ecuación a partir de una solución hallada, e incidentalmente este método, cuando se considera con cuidado, es absolutamente equivalente al método descrito en la sección anterior.