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: $\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}$ on $s_{n}$ i $t_{n}$ són els coeficients de la igualtat: $m c d (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.

Exemple

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