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$$