Ecuación diofántica lineal

Una ecuación diofántica es una ecuación del tipo: $$$a\cdot x+ b\cdot y=c$$$ donde $$a$$, $$b$$ y $$c$$ son tres números enteros, y se pide que la soluciones $$x$$ e $$y$$ también sean enteras.

Las ecuaciones diofánticas no siempre tienen solución. De hecho, una ecuación diofántica sólo tiene solución si el término independiente (la $$c$$) es divisible por el máximo común divisor de $$a$$ y $$b$$.

En este caso existen infinitas soluciones, que vienen dadas por: $$$\displaystyle \begin{array}{rcl} x & = & \frac{c}{mcd(a,b)} s_n+\frac{b}{mcd(a,b)}k \\ y &=& \frac{c}{mcd(a,b)} t_n+\frac{a}{mcd(a,b)}k\end{array}$$$donde $$s_n$$ y $$t_n$$ son los coeficientes de la igualdad: $$$mcd(a,b)=a\cdot s_n + b\cdot t_n$$$ encontrada mediante el algoritmo de Euclides, y $$k$$ es un número entero cualquiera.

Una aplicación interesante de las ecuaciones diofánticas es que permiten solucionar problemas de la vida cotidiana.

Supongamos que un señor va a comprar un libro que cuesta $$23$$ €. No obstante, cuando va a pagar se da cuenta que sólo tiene monedas de $$2$$ €. Por si fuera poco, el cajero en aquel momento sólo tiene billetes de $$5$$ €. ¿Es posible que pueda pagar el precio exacto del libro?

Pues bien, esto se resuelve mediante la siguiente ecuación diofántica: $$$2\cdot x-5\cdot y=23$$$

La $$x$$ representa cuántas monedas de $$2$$ tiene que darle el señor al cajero, y la $$y$$ cuántos billetes de $$5$$ € tiene que devolverle de cambio el cajero, para que lo que esté pagando el señor sean exactamente $$23$$ €.

Está claro que la $$x$$ y la $$y$$ tienen que ser enteras, ya que el señor no puede dar, por ejemplo, $$6$$ monedas y media, o el cajero no puede devolverle $$1.33$$ billetes.

Pues bien, como se ha visto anteriormente, la ecuación diofántica tiene solución puesto que $$mcd(2,5)=1$$, que divide a $$23$$. Además una solución, que se puede encontrar mediante el método anterior, es $$x = 14$$ e $$y = 1$$.

Es decir, el señor tiene que dar al cajero $$14$$ monedas de $$2$$ €, y éste tiene que devolverle un billete de $$5$$ €: $$$2 \cdot 14-5\cdot 1=23$$$