Resolución de Congruencias Lineales

Teoría

Una congruencia lineal es un enunciado matemático de la forma $ax \equiv b \pmod n$, donde $a$, $b$ y $n$ son enteros, $n > 0$, y $x$ es un entero desconocido que tienes que encontrar. Resolver esta congruencia es lo mismo que encontrar todos los enteros $x$ tales que $ax - b$ sea divisible entre $n$. Este problema está ligado de forma fundamental con las Ecuaciones Diofánticas Lineales; resolver $ax \equiv b \pmod n$ es idéntico a resolver la ecuación $ax + ny = b$ para enteros $x$ y $y$.

Este concepto es una pieza clave de la teoría de números elemental y aparece seguido en competencias como el AMC 12 y el AIME. Generaliza las ecuaciones lineales algebraicas estándar a la aritmética modular. La clave para resolver estas congruencias está en el máximo común divisor, $d = \gcd(a, n)$. A diferencia del álgebra estándar de números reales donde $ax=b$ siempre tiene una solución única (para $a \neq 0$), una congruencia lineal puede no tener soluciones, tener una solución única o varias soluciones distintas módulo $n$, dependiendo totalmente de la relación entre $d$ y $b$.

Cuando $\gcd(a, n) = 1$, el entero $a$ tiene un inverso multiplicativo modular, lo que garantiza una solución única. Sin embargo, cuando $\gcd(a, n) > 1$, primero tienes que revisar una condición de existencia. Si existen soluciones, a menudo puedes simplificar la congruencia dividiendo todos los términos entre su máximo común divisor, reduciendo el problema a un módulo con una solución única, que luego se "eleva" a múltiples soluciones en el módulo original.

Fórmulas Clave

La Congruencia Lineal Estándar $$ax \equiv b \pmod n$$ Toma $d = \gcd(a, n)$.

Existencia de Soluciones La congruencia tiene soluciones si y solo si $d$ divide a $b$: $$d \mid b$$ Si $d \nmid b$, no hay soluciones.

Número de Soluciones Si $d \mid b$, hay exactamente $d$ soluciones distintas módulo $n$.

La Solución General Si se cumple la condición $d \mid b$, las soluciones están dadas por: $$x \equiv x_0 + t \cdot \frac{n}{d} \pmod n$$ donde $t \in {0, 1, \dots, d-1}$ y $x_0$ es una solución particular de la congruencia simplificada: $$\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{n}{d}}$$

Caso Especial: Módulo Coprimo Si $\gcd(a, n) = 1$, hay exactamente una solución única módulo $n$: $$x \equiv a^{-1}b \pmod n$$ donde $a^{-1}$ es el inverso multiplicativo modular de $a$ módulo $n$ (que seguido puedes encontrar con el Algoritmo de Euclides Extendido).

Demostración

Teorema: La congruencia lineal $ax \equiv b \pmod n$ tiene soluciones si y solo si $d \mid b$, donde $d = \gcd(a, n)$. Si existen soluciones, hay exactamente $d$ soluciones módulo $n$.

Demostración:

Paso 1: Equivalencia con una Ecuación Diofántica Lineal Por la definición de congruencia, $ax \equiv b \pmod n$ significa que $n$ divide a $ax - b$. Por lo tanto, existe un entero $y$ tal que: $$ax - b = ny \implies ax - ny = b$$ Toma $y' = -y$. Puedes reescribir esto como la Ecuación Diofántica Lineal: $$ax + ny' = b$$

Paso 2: Condición de Existencia Sea $d = \gcd(a, n)$. Por definición, $d \mid a$ y $d \mid n$. Como $d$ divide tanto a $a$ como a $n$, debe dividir a cualquier combinación lineal de ellos. Así, $d \mid (ax + ny')$. En consecuencia, para que la ecuación se cumpla, debes tener que $d \mid b$.

• Si $d \nmid b$, no existen soluciones enteras.
• Si $d \mid b$, por la Identidad de Bezout, existen enteros $x_1, y_1$ tales que $ax_1 + ny_1 = d$. Como $b$ es un múltiplo de $d$ (digamos $b = kd$), puedes multiplicar por $k$ para obtener $a(kx_1) + n(ky_1) = kd = b$, lo que prueba que las soluciones existen.

Paso 3: Caracterización de las Soluciones Supón que $d \mid b$. Divide la ecuación diofántica $ax + ny' = b$ entre $d$: $$\frac{a}{d}x + \frac{n}{d}y' = \frac{b}{d}$$ Toma $a' = a/d$, $n' = n/d$ y $b' = b/d$. Nota que $\gcd(a', n') = 1$. $$a'x + n'y' = b' \implies a'x \equiv b' \pmod{n'}$$ Como $\gcd(a', n') = 1$, $a'$ tiene un inverso único módulo $n'$. Así que hay una solución única para $x$ módulo $n'$. A esta solución específica la vamos a llamar $x_0$.

Paso 4: Conteo de Soluciones Módulo $n$ La solución general para $x$ en los enteros está dada por: $$x = x_0 + t \cdot n' = x_0 + t \cdot \frac{n}{d}$$ donde $t$ es cualquier entero. Estás buscando soluciones distintas módulo $n$. Dos soluciones $x_1, x_2$ son distintas módulo $n$ si $x_1 \not\equiv x_2 \pmod n$. Considera el conjunto de soluciones generado por $t = 0, 1, \dots, d-1$: $$S = \left{ x_0, x_0 + \frac{n}{d}, x_0 + 2\frac{n}{d}, \dots, x_0 + (d-1)\frac{n}{d} \right}$$

1. ¿Son soluciones? Sí, porque para cualquier $k \in S$, $a'k \equiv b' \pmod{n'}$ implica que $ak \equiv b \pmod{n'd}$, que es $ak \equiv b \pmod n$.
2. ¿Son distintas módulo $n$? Supón que dos valores corresponden a $t_1$ y $t_2$ con $0 \le t_1 < t_2 \le d-1$. Si $x_0 + t_1 \frac{n}{d} \equiv x_0 + t_2 \frac{n}{d} \pmod n$, entonces: $$(t_2 - t_1) \frac{n}{d} \equiv