title: Equazione diofantea lineare
text: # 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.$.
  
  