
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≡1(mod5).
Solución. Como sabemos x≡0,1,2,3 o 4(mod5) para cualquier número x. Entonces, al multiplicar por 2 obtenemos que 2x≡0,2,4,1 o 3(mod5), en consecuencia, sólo cuando x≡3(mod5) se satisfacerá la congruencia 2x≡1(mod5). 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≡4(mod6).
Solución. De manera similar, sabemos que x≡0,1,2,3,4, o 5(mod6) para todo número x. Lo que significa que 2x≡0,2,4,0,2, o 4(mod6), en consecuencia, las únicas posibilidad se dan cuando x≡2 o 5(mod6). 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≡3(mod6).
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≡b(modm) 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≡4(mod6), podríamos decir, que 8 y -1 son las soluciones de esta ecuación, pues finalmente 8≡2(mod6) y 5≡−1(mod6).
Más formalmente, decimos que x1,x2,…,xk son las soluciones de la ecuación ax≡b(modm), si se satisface que:
- axi≡b(modm) para todo i
- Para cualquier solución x de la ecuación, existe exactamente un i tal que x≡xi(modm),
La primera condición dice que los números x1,x2,…,xk 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≡b(modm) 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 x0, entonces ax0−b será un múltiplo de m, es decir, ax0−b=km para algún entero k. Luego tenemos que ax0−ḱ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 x0 y y0 tales que ax0+my0=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(kx0)+m(ky0)=b.
Aplicando módulo m tendremos que a(kx0)≡b(modm) y por lo tanto kx0 es solución de la ecuación de ax≡b(modm).
Esto termina la primera parte, ahora sólo nos falta demostrar que son exactamente (a,m)=g. Denotemos con x1 una solución cualquiera, demostraremos primero que x1+(m/g)∗t con t=0,1,…,g−1 son todas las solución. Efectivamente son soluciones, pues a(x1+(m/g)t)=ax1+(a/g)mt≡ax1≡b(modm).
Ahora verifiquemos que cualquier solución tiene que tener dicha forma. Denotemos con x una solución genérica, deberá satisfacer que ax≡ax1(modm), es decir que, a(x1−x)≡0(modm). Ahora, dividiendo entre g obtenemos a/g(x1−x)≡0(modm/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≡x1(modm/g). La anterior ecuación es equivalente a decir que x tiene la forma x=x1+t(m/g) para alguna t
El parámetro t se debe reducir módulo g, pues t≡t0(modg) si y sólo si x1+t(m/g)≡x1+t0(m/g)(modm). Ésto termina la prueba