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: $\begin{array}{rcl} x & = & \frac{c}{m c d (a, b)} s_{n} + \frac{b}{m c d (a, b)} k \\ y & = & \frac{c}{m c d (a, b)} t_{n} + \frac{a}{m c d (a, b)} k \end{array}$ donde $s_{n}$ y $t_{n}$ son los coeficientes de la igualdad: $m c d (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.

Ejemplo

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 $m c d (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$