# Equazione diofantea lineare

Un'equazione diofantea lineare è un'equazione diofantea in cui le relazioni tra le variabili sono di tipo lineare.

## Equazione diofantea lineare in due variabili
### Criterio di risolubilità

Prima di esaminare alcuni metodi di risoluzione delle equazioni diofantee lineari, vediamo un criterio per la loro risolubilità.
Teorema
Siano $a$, $b$, $c$ numeri interi.
L'equazione $ax+by=c$ ha soluzioni intere se e solo se $c$ è divisibile per il massimo comun divisore di $a$ e $b$, cioè se e solo se $\operatorname {MCD} \left(a,b\right)\mid c$.
Dimostrazione
Sia $d:=\operatorname {MCD} (a,b)$ e ricordiamo che l'identità di Bézout afferma che esistono due numeri interi $x_{0}$ e $y_{0}$ tali che
    $ax_{0}+by_{0}=d$.
Supponiamo che $d$ divida $c$. Moltiplichiamo entrambi i membri dell'equazione per il numero intero ${\tfrac {c}{d}}$ ed otteniamo
    $a\left({\frac {c}{d}}\,x_{0}\right)+b\left({\frac {c}{d}}\,y_{0}\right)={\frac {c}{d}}\,d=c;$
se ne conclude che la coppia $\left({\tfrac {c}{d}}\,x_{0},{\tfrac {c}{d}}\,y_{0}\right)$ è soluzione dell'equazione diofantea.
Supponiamo viceversa che l'equazione possegga una soluzione data dalla coppia $\left(x_{1},y_{1}\right)$. L'espressione $ax_{1}+by_{1}$ è una combinazione lineare di interi divisibili per $d$ e quindi fornisce un intero, uguale a $c$, divisibile per tale intero. (c.v.d.)

### Riducibilità ai coefficienti coprimi

Ogni equazione diofantea risolubile, che scriviamo $ax+by=c$, si può ridurre ad un'equazione diofantea della forma ${\tilde {a}}x+{\tilde {b}}y={\tilde {c}}$ avente i coefficienti coprimi.
Abbiamo infatti che, se poniamo:$d:=\operatorname {MCD} (a,b),\,{\tilde {a}}:=a/d,\,{\tilde {b}}:=b/d$
otteniamo
    $(d{\tilde {a}})x+(d{\tilde {b}})y=c$
    $d({\tilde {a}}x+{\tilde {b}}y)=c$
    ${\tilde {a}}x+{\tilde {b}}y={\frac {c}{d}}=:{\tilde {c}}$
in cui $\operatorname {MCD} ({\tilde {a}},{\tilde {b}})=1$.

### Risoluzione con l'algoritmo di Euclide

Vediamo ora un metodo risolutivo che si basa sull'algoritmo di Euclide per la ricerca del massimo comun divisore fra due o più numeri interi.
Procediamo per gradi e prima di risolvere l'equazione "ridotta" $ax+by=c$ con $\operatorname {MCD} (a,b)=1$, occupiamoci della risoluzione dell'equazione "particolare" $ax+by=1$.
Possiamo supporre che $a$ sia maggiore di $b$ e implementiamo l'algoritmo di Euclide. Poniamo $a=r_{1}$ e $b=r_{2}$:
    $r_{1}=q_{1}r_{2}+r_{3}$ con $0<r_{3}<r_{2}$
    $r_{2}=q_{2}r_{3}+r_{4}$ con $0<r_{4}<r_{3}$
$\cdots \cdots \cdots \cdots \cdots$
    $r_{n-4}=q_{n-4}r_{n-3}+r_{n-2}$ con $0<r_{n-2}<r_{n-3}$
    $r_{n-3}=q_{n-3}r_{n-2}+r_{n-1}$ con $0<r_{n-1}<r_{n-2}$
$r_{n-2}=q_{n-2}r_{n-1}+1$.
L'ultimo resto è $1$ in accordo con il fatto che $a$ e $b$ sono primi fra loro. Dobbiamo ora ottenere una rappresentazione di $ax+by=1$ tramite un processo che deriva dall'algoritmo. Iniziamo dal fondo e scriviamo $1$ come combinazione lineare di $r_{n-1}$ e $r_{n-2}$
$1=r_{n-2}-q_{n-2}r_{n-1}$.
La penultima equazione $r_{n-3}=q_{n-3}r_{n-2}+r_{n-1}$ è equivalente a
    $r_{n-1}=r_{n-3}-q_{n-3}r_{n-2}$,
e, sostituendo la penultima nell'ultima, otteniamo
    $1=r_{n-2}-q_{n-2}r_{n-1}=r_{n-2}-q_{n-2}(r_{n-3}-q_{n-3}r_{n-2})=-q_{n-2}r_{n-3}+(1+q_{n-2}q_{n-3})r_{n-2}$.
Abbiamo così ottenuto $1$ come combinazione lineare di $r_{n-3}$ e di $r_{n-2}$.
Dalla terz'ultima equazione $r_{n-4}=q_{n-4}r_{n-3}+r_{n-2}$ abbiamo che
    $r_{n-2}=r_{n-4}-q_{n-4}r_{n-3}$
e, analogamente a quanto fatto in precedenza, otteniamo $1$ come combinazione lineare di $r_{n-4}$ e di $r_{n-3}$.
Il processo continua fino a quando si arriva ad avere $1$ come combinazione lineare di $r_{1}=a$ e di $r_{2}=b$. I coefficienti della combinazione lineare, che indichiamo con $~x_{0}~$ e $~y_{0}~$, costituiscono una soluzione dell'equazione $~ax+by=1~$.
Partiamo ora dall'uguaglianza che sappiamo essere vera $~ax_{0}+by_{0}=1~$ e moltiplichiamo entrambi i membri per $~c~$
$~c(ax_{0}+by_{0})=c\cdot 1$
$~cax_{0}+cby_{0}=c~$
$~a(cx_{0})+b(cy_{0})=c~$.
Questo equivale a dire che la coppia $~(cx_{0},cy_{0})~$ è soluzione dell'equazione $~ax+by=c~$.
La soluzione trovata non è l'unica soluzione dell'equazione $~ax+by=c~$. Infatti abbiamo
$~ax+by=c~$
$~ax+by=a(cx_{0})+b(cy_{0})~$
$~a(x-cx_{0})=-b(y-cy_{0})~$.
Questa uguaglianza mostra che il prodotto $~a(x-cx_{0})~$ è divisibile per $~b~$. Dal momento che $~a~$ e $~b~$ sono primi fra loro, possiamo concludere che $~(x-cx_{0})~$ è divisibile per $~b~$, ovvero esiste un intero $~t~$ tale che $~x-cx_{0}=tb~$. Sostituendo questa relazione nella precedente otteniamo:
$~a(x-cx_{0})=-b(y-cy_{0})~$
$~a(tb)=-b(y-cy_{0})~$
ovvero $~y-cy_{0}=-ta~$.
In conclusione le soluzioni dell'equazione $~ax+by=c~$ sono date da
$\left\{{\begin{matrix}x=cx_{0}+tb\\\\y=cy_{0}-ta\\\end{matrix}}\right.$
con $~t~$ intero.

#### Esempio

Applichiamo il metodo descritto all'equazione $~8x+5y=81~$. Consideriamo quindi l'equazione $~8x+5y=1~$ e implementiamo l'algoritmo di Euclide alla coppia $~8~$ e $~5~$:
$8~=~5\cdot 1+3$
$5~=~3\cdot 1+2$
$3~=~2\cdot 1+1\,.$
Riscriviamo le tre uguaglianze mettendo in evidenza i resti
$3~=~8-5\cdot 1$
$2~=~5-3\cdot 1$
$1~=~3-2\cdot 1\,.$
Partiamo dall'ultima e sostituiamo a ritroso i valori:
$~1=3-2=3-(5-3)=3-5+3=2\cdot 3-5=2\cdot (8-5)-5=2\cdot 8-2\cdot 5-5=2\cdot 8-3\cdot 5~$.
Quindi abbiamo $~x=2~$ e $~y=-3~$.
Una volta trovata una soluzione dell'equazione $~8x+5y=1~$, che indichiamo con $~(x_{0},y_{0})~$, per ottenere una soluzione dell'equazione $~8x+5y=81~$ bastano tre moltiplicazioni per uno stesso fattore.
Moltiplicando per $~81~$ i due membri di $~2\cdot 8-3\cdot 5=1~$, otteniamo che una soluzione dell'equazione $~8x+5y=81~$ è data dalla coppia $~(2\cdot 81,-3\cdot 81)=(162,-243)~$.
La soluzione generale dell'equazione $~8x+5y=81~$ è data da
$\left\{{\begin{matrix}x=162-5t\\\\y=-243+8t\,.\\\end{matrix}}\right.$

### Risoluzione con le frazioni continue

Mostriamo ora come si possano usare le frazioni continue per risolvere l'equazione diofantea $~ax+by=c~$. Il nostro avvicinamento a questa meta avverrà gradualmente, attraverso facili passaggi, che culmineranno infine nel metodo per la risoluzione di ogni equazione risolubile della forma $~ax+by=c~$.

#### L'equazione indeterminata ax-by=±1

Impariamo dapprima a risolvere l'equazione $~ax-by=1~$ con $~\mathrm {MCD} (a,b)=1~$.
Teorema
L'equazione $~ax-by=1~$, dove $~a~$ e $~b~$ sono interi positivi primi fra loro, ha infinite soluzioni intere $~(x,y)~$.
Dimostrazione
Trasformiamo dapprima ${\frac {a}{b}}$ in una frazione continua aritmetica limitata o semplice
${\frac {a}{b}}=[\,a_{1};a_{2},\ldots ,a_{n-1},a_{n}\,]\,,$
e calcoliamo le ridotte $c_{1},c_{2},\ldots ,c_{n-1},c_{n}$.
Le ultime due
$c_{n-1}={\frac {p_{n-1}}{q_{n-1}}}\,,\ \ \ \ \ \ c_{n}={\frac {p_{n}}{q_{n}}}={\frac {a}{b}}\,,$
sono la chiave della soluzione. Queste infatti soddisfano la relazione fondamentale
$~p_{n}q_{n-1}-p_{n-1}q_{n}=(-1)^{n}~$
e poiché $~p_{n}=a~$ e $~q_{n}=b~$, si ha
$~aq_{n-1}-bp_{n-1}=(-1)^{n}~$.
Se $~n~$ è pari, cioè se abbiamo un numero pari di quozienti parziali $a_{1},a_{2},\ldots ,a_{n}$, $~(-1)^{n}=1~$ e l'ultima equazione scritta diventa
$~aq_{n-1}-bp_{n-1}=1~$.
Confrontando questa con l'equazione data $~ax-by=1~$, si vede che una soluzione di questa è
$x_{0}=q_{n-1}\,,\ \ \ \ \ \ y_{0}=p_{n-1}$.
Questa, tuttavia, è una soluzione particolare e non la soluzione generale. Indicheremo le soluzioni particolari con $~(x_{0},y_{0})~$. D'altra parte se $~n~$ è dispari così che $~(-1)^{n}=-1~$, possiamo modificare lo sviluppo
${\frac {a}{b}}=[\,a_{1};a_{2},\ldots ,a_{n-1},a_{n}\,]$
sostituendo
${\frac {1}{a_{n}}}$ con ${\cfrac {1}{(a_{n}-1)+{\cfrac {1}{1}}}}$ se $~a_{n}>1~$
o sostituendo
${\cfrac {1}{a_{n-1}+{\cfrac {1}{a_{n}}}}}$ con ${\cfrac {1}{a_{n-1}+1}}$ se $~a_{n}=1~$.
Cioè, se lo sviluppo ha un numero dispari di quozienti parziali, si può trasformare in $[\,a_{1};a_{2},\ldots ,a_{n-1},a_{n}-1,1\,]$ se $~a_{n}>1~$ o in $[\,a_{1};a_{2},\ldots ,a_{n-1}+1\,]$ se $~a_{n}=1~$; in entrambi i casi il numero dei quozienti diviene pari.
Usando questa frazione continua, in entrambi i casi, ricalcoliamo ${\frac {p_{n-1}}{q_{n-1}}}$, ${\frac {p_{n}}{q_{n}}}={\frac {a}{b}}$ e l'equazione $~aq_{n-1}-bp_{n-1}=1~$ è di nuovo soddisfatta.
Come già visto nella sezione precedente la soluzione generale è
$\left\{{\begin{matrix}x=x_{0}+tb&&\\&&t=0,\pm 1,\pm 2,\pm 3,\ldots \,.\\y=y_{0}+ta&&\end{matrix}}\right.$ (c.v.d.)

#### Esempio

Trovare le soluzioni intere dell'equazione indeterminata $~205x-93y=1~$.
Qui gli interi $~205=5\cdot 41~$ e $~93=3\cdot 31~$ sono primi fra loro e l'equazione ha soluzioni intere. La frazione continua corrispondente a $~{\frac {205}{93}}~$ cioè $[\,2;4,1,8,2\,]$ ha un numero dispari di quozienti parziali, ma può essere sostituita da $~{\frac {205}{93}}=[\,2;4,1,8,1,1\,]~$, sviluppo equivalente con un numero pari di quozienti. Calcoliamone le ridotte.
${\begin{matrix}i&-1&0&1&2&3&4&5&6\\a_{i}&&&2&4&1&8&1&1\\p_{i}&0&1&2&9&11&97&108&205\\q_{i}&1&0&1&4&5&44&49&93\\c_{i}&&&{\cfrac {2}{1}}&{\cfrac {9}{4}}&{\cfrac {11}{5}}&{\cfrac {97}{44}}&{\cfrac {108}{49}}&{\cfrac {205}{93}}\\\end{matrix}}$
Qui $~n=6~$, $~p_{n-1}=p_{5}=108=y_{0}~$, $~q_{n-1}=q_{5}=49=x_{0}~$, e quindi, per la
$\left\{{\begin{matrix}x=x_{0}+tb&&\\&&t=0,\pm 1,\pm 2,\pm 3,\ldots \,.\\y=y_{0}+ta&&\end{matrix}}\right.$,
la soluzione generale dell'equazione è
$\left\{{\begin{matrix}x=x_{0}+tb=49+93t&&\\&&t=0,\pm 1,\pm 2,\pm 3,\ldots \,.\\y=y_{0}+ta=108+205t&&\end{matrix}}\right.$

#### Osservazione

Il metodo per risolvere l'equazione $~ax-by=-1~$ con $~\mathrm {MCD} (a,b)=1~$ è del tutto analogo a quello usato per risolvere l'equazione $~ax-by=+1~$ con $~\mathrm {MCD} (a,b)=1~$.
Basta trasformare $~{\frac {a}{b}}~$ in una frazione continua aritmetica limitata con un numero dispari di ridotte.

### La soluzione generale di ax-by=c con MCD(a,b)=1

Imparato a risolvere l'equazione $~ax-by=1~$ dove $~a~$ e $~b~$ sono interi primi fra loro, è facile risolvere l'equazione $~ax-by=c~$ nella quale $~c~$ è intero. Come abbiamo già visto nei paragrafi precedenti la soluzione generale di $~ax-by=c~$ è
$\left\{{\begin{matrix}x=cx_{0}+bt&&\\&&t=0,\pm 1,\pm 2,\pm 3,\ldots \,.\\y=cy_{0}+at&&\end{matrix}}\right.$

### La soluzione generale di ax+by=c con MCD(a,b)=1

La discussione di questa equazione è simile, ad eccezione di alcune lievi modifiche, a quella dell'equazione $~ax-by=c~$. Sempre supponendo che $~a~$ e $~b~$ siano interi positivi, troviamo dapprima una soluzione particolare dell'equazione $~ax+by=c~$ con $~\mathrm {MCD} (a,b)=1~$.
Per fare ciò, sviluppiamo $~{\frac {a}{b}}~$ in frazione continua con un numero pari di quozienti parziali.
Dalla tavola delle ridotte prendiamo $~p_{n-1}~$ e $~q_{n-1}~$. Allora vale $~aq_{n-1}-bp_{n-1}=1~$, come in precedenza.
L'artificio consiste ora nello scrivere l'equazione data nella forma
$~ax+by=c\cdot 1=c(aq_{n-1}-bp_{n-1})~$.
Cambiamo l'ordine dei termini ed otteniamo
$~a(cq_{n-1}-x)=b(y+cp_{n-1})~$.
Quindi $~b~$ divide la quantità che figura a sinistra; ma $~\mathrm {MCD} (a,b)=1~$ e quindi $~b~$, che non ha divisori comuni con $~a~$ (salvo $~1~$), deve dividere $~cq_{n-1}-x~$ che equivale a dire che esiste un intero $~t~$ tale che
$~cq_{n-1}-x=tb~$
o anche che
$~x=cq_{n-1}-tb~$.
Sostituendo si ottiene
$~a(tb)=b(y+cp_{n-1})~$
la quale, risolta nella variabile $~y~$, dà
$~y=at-cp_{n-1}~$.
Viceversa, qualunque sia l'intero $~t~$, sostituendo in $~ax+by~$ si ha
$~ax+by=a(cq_{n-1}-tb)+b(at-cp_{n-1})=c(aq_{n-1}-bp_{n-1})=c\cdot 1=c~$
e l'equazione $~ax+by=c~$ è soddisfatta.
Quindi la sua soluzione generale è
$\left\{{\begin{matrix}x=cq_{n-1}-tb&&\\&&t=0,\pm 1,\pm 2,\pm 3,\ldots \,.\\y=-cp_{n-1}+at&&\end{matrix}}\right.$

#### Esempio

Risolviamo ora con le frazioni continue l'equazione diofantea $~8x+5y=81~$. Sviluppiamo $~{\frac {8}{5}}~$ in frazione continua, ottenendo $~{\frac {8}{5}}=1+{\frac {3}{5}}=1+{\cfrac {1}{\cfrac {5}{3}}}=1+{\cfrac {1}{1+{\cfrac {2}{3}}}}=1+{\cfrac {1}{1+{\cfrac {1}{\cfrac {3}{2}}}}}=1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{2}}}}}}~$
Quindi $~{\frac {8}{5}}=[1;1,1,2]~$. La frazione ha un numero pari di coefficienti parziali, quindi non dobbiamo modificarla. Le ridotte della frazione continua sono: $~1\,,2\,,{\frac {3}{2}}\,,{\frac {8}{5}}~$.
In conclusione la soluzione generale dell'equazione diofantea $~8x+5y=81~$ è data da
$\left\{{\begin{matrix}x=81\cdot 2-5t=162-5t&&\\&&t=0,\pm 1,\pm 2,\pm 3,\ldots \,.\\y=-81\cdot 3+8t=-243+8t&&\end{matrix}}\right.$.