10.4 Ecuaciones lineales diofantinas.

Una ecuación lineal diofantina es una ecuación de la forma
ax +by = c
donde a,b,c son números enteros y x, y son variables que toman valores enteros.
Veamos algunos ejemplos:
La ecuación 4x-6y=5 no tiene soluciones enteras, ya que sin importar el valor de x y y el lado izquierdo siempre es un número par, mientras que el derecho es un número impar.
La ecuación 4x-6y =2 tiene solución , ya que (4,6)=2 y entonces existe una combinación lineal de 4 y 6 que es igual a dos.
La ecuación 4x- 6y = 10 tiene solución . Si x₀ y y₀ son solución de 4x –6y =2 entonces 5x₀ y 5y₀ son solución de 4x- 6y = 10.
Podemos generalizar los últimos dos ejemplos. Si d = (a,b) sabemos que existen enteros x₀, y₀ tales que ax₀ + by₀ = d, es decir, la ecuación.
ax + by =(a,b)
Siempre tiene solución.
Más aún si c es un múltiplo de d (por ejemplo c =kd) entonces
a (kx₀) + b(ky₀) = k (ax₀ +by ₀)= kd =c
es decir, una ecuación de la forma
ax +by = k (a,b)
siempre tiene solución. Esto constituye el primer teorema de la sección.
Teorema 10.19 Si (a,b)| c entonces la ecuación lineal diofantina
Ax +by = c
Siempre tiene solución entera.
Un corolario muy importante es:
Corolario 10.20Si a y b son primos relativos, la ecuación ax +by =c siempre tiene solución entera.
Ahora nos preguntamos: ¿Habrá alguna ecuación lineal ax +by =c que tenga solución y en donde (a,b) no divida a c?
Vamos a restringirnos únicamente al caso en que c es positivo, puesto que si u y v son solución de ax + by = c entonces –u y –v son solución de ax +by = -c.
Por un lado, como (a,b) es la mínima combinación lineal positiva si c = 1,2,...,(a,b)-1 la ecuación ax +by = c no puede tener solución. De esta manera, si existe una solución, necesariamente c ≥ (a,b).
Supongamos que la ecuación ax +by = c tiene como solución a x₁ y y₁ , que d =(a,b), no divide a c, y sean x₀ y y₀ una solución para ax + by =d. De esta manera tenemos
ax₁ +by₁ =c
ax₀ +by₀ =d
Por el algoritmo de la división tenemos c = md +r con 0 < r < c puesto que d no divide a c. Entonces:
ax+ by = md +r
= m (ax₀ + by₀ ) +r
=a (mx₀) +b (my₀)+r
y por tanto
a(x₁- mx₀) + b (y₁-my₀) = r.
¡Lo anterior es una contradicción! Puesto que tenemos una combinación lineal positiva de a y b igual a r y 0 < r < d, eso contradice que d era la combinación lineal mínima positiva (es decir, d no era el máximo común divisor). La contradicción surgió de suponer que ax + by =c podía tener solución aunque (a,b) no dividiera a c, por lo que hemos demostrado el siguiente teorema.
Teorema 10.21La ecuación lineal diofantina
Ax +by = c
Tiene solución si y solo si (a,b) |c

Ya estamos en condición de determinar si una ecuación dada tiene solución o no, ahora nos interesa determinar cuales son las soluciones. Supongamos que la ecuación ax +by =c tiene solución, es decir c = kd donde d= (a,b).
Si u y v son una solución de ax +by =d, entonces x ₀ =k y y₀ =kv son una solución de ax + by =c. De este modo podemos encontrar al menos una solución a la ecuación . Sea x₁, y₁ otra solución. Como x₁ ≠ x₀ existe un entero r tal que x₁ =x₀ +r. Sustituyamos en la ecuación.

a (x₀ +r) +by ₁ = c =ax₀ +by₀
Y al simplificar obtenemos
Un argumento simétrico muestra que si y₁ = y₀-s entonces Una vez más sustituimos en la ecuación

Y al simplificar llegamos a bs-ar= 0. Sean
Entonces (a`,b`) = 1 y (r`,s)`=1 Además
b`s`- a`r`=0.
Esto implica que b`s` =a`r`. Además, la coprimalidad implicara que r’ =b’ y s`=a`.Por tanto tenemos que,
Así toda solución es de la forma
Donde t es un entero que satisface la relación
Para terminar, notemos que

¡Esto quiere decir que todo entero satisface la relación anterior! En otras palabras , los números de la forma x =x₀ +bt/d y y=y₀-at/d siempre son soluciones y además toda pareja de números que es de esa forma es solución.

Para recapitular todo el trabajo desarrollado en esta sección establecemos el teorema principal.
Teorema 10.22 (Resolución de la ecuación lineal de congruencia.)
La ecuación ax +by =c tiene solución si y solo si d = (a,b) divide a c. Además , las soluciones son los números de la forma
Donde x₀ y y₀ son una solución particular y t es cualquier número entero.