Ecuaciones Diofantinas Lineales

La ecuación diofantina $ax+by=c$

Diofantos fue un matemático que vivió en Alexandria al rededor de 250 a.c. Él fue el primero en estudiar soluciones a ecuaciones del tipo $ax+by=c$ en los enteros. Al morir en su lápida aprarece la leyenda:

Su infancia duró $1/6$ de su vida. Su barba creció después de $1/12$ de su vida más y después de $1/7$ más se casó. Su primer hijo nació 5 años después, su hijo vivio sólo la mitad de la vida de su padre y el padre murió 4 años después que su hijo.

Definición: Una ecuación diofantinas es una ecuación del a forma $ax+by=c$ con $a,b,c$ enteros dados y $x,y$ incógnitas. Una solución de esta ecuación es un par de enteros $x_0,y_0$ que satisfacen la ecuación.

Por ejemplo, dada la ecuación $3x+6y=18$ tenemos distintas soluciones:

(1)
\begin{align} 3(4)+6(1)=18\\ 3(-6)=6(6) = 18 3(10)+ 6(-2)=18 \end{align}

Sin embargo, $2x+10y = 17$ no tiene soluciones en los enteros. Por ejemplo podemos decir que el lado izquierdo siempre será un número par, mientras que el derecho es impar.

Proposición: La ecuación $ax+by=c$ tiene solución si y sólo si, $d=(a,b)$ divide a $c$.

Demostración: En efecto, habíamos visto que el conjunto

(2)
\begin{align} T = \left\{ ax+by | x,y\in \mathbb{Z} \right\} \end{align}

coincide con el conjunto de múltiplos de $d=(a,b).$

Ahora supongamos que $d= ax_0 +by_0$ para algunos enteros $x_0, y_0$ entonces si $c=ds$ tenemos que $sx_0, sy_0$ es una solución particular de la ecuación diofantina. De hecho tenemos el siguiente resultado.

Proposición: La ecuación Diofantina $ax+by=c$ tiene solución si y sólo si $d\mid c$ para $d=(a,b)$ y si $x_0, y_0$ es una solución particular a la ecuación, entonces todas las ecuaciones están dadas por $x=x_0 + (b/d)t, y=y_0 - (a/d)t$ variando $t\in \mathbb{Z}$.

Demostración: Claramente con lo expresado en el enunciado obtenemos nuevas soluciones. Ahora supongamos que tenemos dos soluciones distintas:

(3)
\begin{equation} ax+by=c = ax'+by' \end{equation}

entonces $ax+by=ax'+by'$ o $a(x-x')=b(y'-y)$ pero sabemos que $1=(a/d,b/d)=(r,s)$ con $(r,s)=1$ entonces dividiendo entre $d$ obtenemos $r(x-x')=s(y'-y)$ y entonces $r\mid (y'-y)$ es decir $y'=(a/d)t + y$ pero si $rt=(y-y')$ entonces $(x-x')=st$ implicando el resultado.

Esto nos dice que hay una infinidad de soluciones para la ecuación dada. En particular la solución encontrada para $d=ax+by$ vía el algoritmo de Euclides extendido no es única.

Ejemplo: Encuentra las soluciones de $172x +20y = 1000$.

A veces es útil tener una interpretación geométrica del resultado anterior. Es decir de las soluciones de la ecuación $ax+by=c$. Esto nos dice que la gráfica de la ecuación lineal tiene puntos con coordenadas enteres si y solamente si, $d\mid c$ y nos dice cómo son todos estos puntos.

Corolario: Si $(a,b)=1$ y si $x_0, y_0$ es una solución particular, entonces $x=x_0+bt, y=y_0-at$ con $t\in \mathbb{Z}$ nos da todas las soluciones.

Aplicación: Un cliente compra una docena de frutas, que consiste de naranjas y manzanas por un precio de $132 pesos. Si una manzana cuesta 3 pesos más que una naranja. ¿Cuántas naranjas y cuántas manzanas compró?

Si no se indica lo contrario, el contenido de esta página se ofrece bajo Creative Commons Attribution-ShareAlike 3.0 License