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