Equacions diofàntiques lineals

Una equació diofàntica és una equació del tipus: $$a\cdot x+ b\cdot y=c$$ on $a$, $b$ i $c$ són tres números enters, i es demana que les solucions $x$ i $y$ també siguin enteres.

Les equacions diofàntiques no sempre tenen solució. De fet, una equació diofàntica només té solució si el terme independent (la $c$) és divisible pel màxim comú divisor d'$a$ i $b$.

En aquest cas hi ha infinites solucions, que vénen donades per: $$\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}$$ on $s_n$ i $t_n$ són els coeficients de la igualtat: $$mcd(a,b)=a\cdot s_n + b\cdot t_n$$ trobada mitjançant l'algorisme d'Euclides, i $k$ és un nombre enter qualsevol.

Una aplicació interessant de les equacions diofàntiques és que permeten solucionar problemes de la vida quotidiana.

Suposem que un senyor va a comprar un llibre que costa $23$€. No obstant això, quan va a pagar s'adona que només té monedes de $2$ €. Per si fos poc, el caixer en aquell moment només té bitllets de $5$ €. És possible que pugui pagar el preu exacte del llibre?

Doncs bé, això es resol mitjançant la següent equació diofàntica: $$2\cdot x-5\cdot y=23$$

La $x$ representa quantes monedes de $2$ ha de donar-li el senyor al caixer, i la $y$ quants bitllets de $5$€ ha de tornar de canvi el caixer, perquè el que estigui pagant el senyor siguin exactament $23$ €.

Està clar que la $x$ i la $y$ han de ser enteres, ja que el senyor no pot donar, per exemple, $6$ monedes i mitja, o el caixer no pot tornar-li $1.33$ bitllets.

Doncs bé, com s'ha vist anteriorment, l'equació diofàntica té solució ja que $mcd (2,5) = 1$, que divideix $23$. A més una solució, que es pot trobar mitjançant el mètode anterior, és $x = 14$ i $y = 1$.

És a dir, el senyor ha de donar al caixer $14$ monedes de $2$ €, i aquest ha de tornar un bitllet de $5$ €: $$2 \cdot 14-5\cdot 1=23$$