Pare motivar la definición que veremos más adelante resolvamos primero los siguientes problema ejemplos.
Problema 1. Encuentra los números $x$ que satisfacen la congruencia $2x \equiv 1 \pmod{5}$.
Solución. Como sabemos $x \equiv 0,1,2,3 \textrm{ o } 4 \pmod{5}$ para cualquier número $x$. Entonces, al multiplicar por 2 obtenemos que $2x \equiv 0, 2,4,1 \textrm{ o } 3 \pmod {5}$, en consecuencia, sólo cuando $x \equiv 3 \pmod{5}$ se satisfacerá la congruencia $2x \equiv 1 \pmod{5}$. Esto nos determina por completo las soluciones, que serán los números $x$ que dejan residuo 3 al dividirse entre 5.
Problema 2. Encuentra los números $x$ que satisfacen la congruencia $2x \equiv 4 \pmod{6}$.
Solución. De manera similar, sabemos que $x \equiv 0,1,2,3, 4, \textrm{ o } 5 \pmod{6}$ para todo número $x$. Lo que significa que $2x \equiv 0, 2,4,0, 2, \textrm{ o } 4 \pmod {6}$, en consecuencia, las únicas posibilidad se dan cuando $x \equiv 2 \textrm{ o } 5 \pmod{6}$. Entonces las soluciones son los números que dejan residuo 2 o 5 al dividirse entre 6.
Problema 3. Encuentra los números $x$ que satisfacen la congruencia $2x \equiv 3 \pmod{6}$.
Solución. Por el análisis del problema anterior, los residuos posibles de $2x$ son sólo 0, 2 y 4. Entonces esta ecuación no tiene solución.
Al leer con cuidado estos ejercicios, se observa que para dar las soluciones de una ecuación de la forma $ax \equiv b \pmod{m}$ basta con encontrar todos los residuos módulo $m$ que satisfacen la ecuación.
Por cuestiones prácticas de argumentación en demostraciones, es conveniente permitir que los residuos sean dados por números no necesariamente menores al módulo, por ejemplo, en lugar de decir que 2 y 5 son las soluciones de la ecuación $2x \equiv 4 \pmod{6}$, podríamos decir, que 8 y -1 son las soluciones de esta ecuación, pues finalmente $8 \equiv 2 \pmod{6}$ y $5 \equiv -1 \pmod{6}$.
Más formalmente, decimos que $x_1, x_2, \ldots, x_k$ son las soluciones de la ecuación $ax \equiv b \pmod{m}$, si se satisface que:
- $ax_i \equiv b \pmod{m}$ para todo $i$
- Para cualquier solución $x$ de la ecuación, existe exactamente un $i$ tal que $x \equiv x_i \pmod{m}$,
La primera condición dice que los números $x_1, x_2, \ldots, x_k$ son soluciones de la ecuación y la segunda que cualquier otra solución es congruente a una y sólo una de éstas.
Bueno, ahora pasaremos al teorema principal
Teorema principal
Teorema. La ecuación diofantina $ax \equiv b \pmod{m}$ tiene solución si y sólo si $(a,m) | b$. Más aun, si $(a,m) | b$ entonces la ecuación tendrá $(a,m)$ soluciones no congruentes.
Demostración: Supongamos que existe solución $x_0$, entonces $ax_0 -b$ será un múltiplo de $m$, es decir, $ax_0 -b = km$ para algún entero $k$. Luego tenemos que $ax_0 - ḱm = b$ y de aquí se sigue que $(a,m) | b$.
Ahora probemos en la otra dirección, supongamos que $(a,m) | b$ y tratemos de demostrar que existe solución. Llamemos $g = (a,m)$ y por la identidad de Bezout existen enteros $x_0$ y $y_0$ tales que $ax_0 + my_0 = g$. Como $b$ es múltiplo de $g$ tendremos que existe $k$ tal que $b = kg$, entonces multiplicando la expresión del enunciado anterior por $k$ tendremos que: $$a(kx_0) + m(k y_0) = b.$$
Aplicando módulo $m$ tendremos que $a(kx_0) \equiv b \pmod{m}$ y por lo tanto $kx_0$ es solución de la ecuación de $ax \equiv b \pmod{m}$.
Esto termina la primera parte, ahora sólo nos falta demostrar que son exactamente $(a,m)=g$. Denotemos con $x_1$ una solución cualquiera, demostraremos primero que $x_1 + (m/g)*t$ con $t=0,1, \dots, g-1$ son todas las solución. Efectivamente son soluciones, pues $a(x_1+(m/g)t) = ax_1 + (a/g)mt \equiv ax_1 \equiv b \pmod{m}$.
Ahora verifiquemos que cualquier solución tiene que tener dicha forma. Denotemos con $x$ una solución genérica, deberá satisfacer que $ax \equiv ax_1 \pmod{m}$, es decir que, $a(x_1 -x) \equiv 0 \pmod{m}$. Ahora, dividiendo entre $g$ obtenemos $a/g(x_1 -x) \equiv 0 \pmod{m/g}$. Como $a/g$ y $m/g$ son primos relativos (pues les quitamos el máximo común divisor) , podemos cancelar $a/g$ y resulta entonces que $x \equiv x_1 \pmod{m/g}$. La anterior ecuación es equivalente a decir que $x$ tiene la forma $x = x_1 + t(m/g)$ para alguna $t$
El parámetro $t$ se debe reducir módulo $g$, pues $t \equiv t_0 \pmod{g}$ si y sólo si $x_1 + t(m/g) \equiv x_1 + t_0(m/g) \pmod{m}$. Ésto termina la prueba