Ecuación lineal en una variable módulo m

Versión para impresión

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 2x1(mod5).

Solución. Como sabemos x0,1,2,3 o 4(mod5) para cualquier número x.  Entonces, al multiplicar por 2 obtenemos que 2x0,2,4,1 o 3(mod5), en consecuencia, sólo cuando x3(mod5) se satisfacerá la congruencia  2x1(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 2x4(mod6).

Solución. De manera similar, sabemos que x0,1,2,3,4, o 5(mod6) para todo número x.  Lo que significa que 2x0,2,4,0,2, o 4(mod6), en consecuencia, las únicas posibilidad se dan cuando x2 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 2x3(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 axb(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 2x4(mod6), podríamos decir, que 8 y -1 son las soluciones de esta ecuación, pues finalmente 82(mod6) y 51(mod6).

Más formalmente, decimos que x1,x2,,xk son las soluciones de la ecuación axb(modm), si se satisface que:

  • axib(modm) para todo i
  • Para cualquier solución x de la ecuación, existe exactamente un i tal que xxi(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 axb(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 ax0b será un múltiplo de m, es decir, ax0b=km para algún entero k. Luego tenemos que ax0m=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 axb(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,,g1 son todas las solución. Efectivamente son soluciones, pues a(x1+(m/g)t)=ax1+(a/g)mtax1b(modm).

Ahora verifiquemos que cualquier solución tiene que tener dicha forma. Denotemos con x una solución genérica, deberá satisfacer que axax1(modm), es decir que, a(x1x)0(modm). Ahora, dividiendo entre g obtenemos a/g(x1x)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 xx1(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 tt0(modg) si y sólo si x1+t(m/g)x1+t0(m/g)(modm). Ésto termina la prueba