Equazione diofantea lineare

Prima di esaminare alcuni metodi di risoluzione delle equazioni diofantee lineari, vediamo un criterio per la loro risolubilità.

Teorema

Siano ${\displaystyle a}$ , ${\displaystyle b}$ , ${\displaystyle c}$ numeri interi.

L'equazione ${\displaystyle ax+by=c}$ ha soluzioni intere se e solo se ${\displaystyle c}$ è divisibile per il massimo comun divisore di ${\displaystyle a}$ e ${\displaystyle b}$ , cioè se e solo se ${\displaystyle \operatorname {MCD} \left(a,b\right)\mid c}$ .

Dimostrazione

Sia ${\displaystyle d:=\operatorname {MCD} (a,b)}$ e ricordiamo che l'identità di Bézout afferma che esistono due numeri interi ${\displaystyle x_{0}}$ e ${\displaystyle y_{0}}$ tali che

${\displaystyle ax_{0}+by_{0}=d}$ .

Supponiamo che ${\displaystyle d}$ divida ${\displaystyle c}$ .Moltiplichiamo entrambi i membri dell'equazione per il numero intero ${\displaystyle {\tfrac {c}{d}}}$ ed otteniamo

${\displaystyle 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 ${\displaystyle \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 ${\displaystyle \left(x_{1},y_{1}\right)}$ . L'espressione ${\displaystyle ax_{1}+by_{1}}$ è una combinazione lineare di interi divisibili per ${\displaystyle d}$ e quindi fornisce un intero, uguale a ${\displaystyle c}$ , divisibile per tale intero. (c.v.d.)

Ogni equazione diofantea risolubile, che scriviamo ${\displaystyle ax+by=c}$ , si può ridurre ad un'equazione diofantea della forma ${\displaystyle {\tilde {a}}x+{\tilde {b}}y={\tilde {c}}}$ avente i coefficienti coprimi.

Abbiamo infatti che, se poniamo:${\displaystyle d:=\operatorname {MCD} (a,b),\,{\tilde {a}}:=a/d,\,{\tilde {b}}:=b/d}$

otteniamo

${\displaystyle (d{\tilde {a}})x+(d{\tilde {b}})y=c}$

${\displaystyle d({\tilde {a}}x+{\tilde {b}}y)=c}$

${\displaystyle {\tilde {a}}x+{\tilde {b}}y={\frac {c}{d}}=:{\tilde {c}}}$

in cui ${\displaystyle \operatorname {MCD} ({\tilde {a}},{\tilde {b}})=1}$ .

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" ${\displaystyle ax+by=c}$ con ${\displaystyle \operatorname {MCD} (a,b)=1}$ , occupiamoci della risoluzione dell'equazione "particolare" ${\displaystyle ax+by=1}$ .

Possiamo supporre che ${\displaystyle a}$ sia maggiore di ${\displaystyle b}$ e implementiamo l'algoritmo di Euclide. Poniamo ${\displaystyle a=r_{1}}$ e ${\displaystyle b=r_{2}}$ :

${\displaystyle r_{1}=q_{1}r_{2}+r_{3}}$ con ${\displaystyle 0<r_{3}<r_{2}}$

${\displaystyle r_{2}=q_{2}r_{3}+r_{4}}$ con ${\displaystyle 0<r_{4}<r_{3}}$

${\displaystyle \cdots \cdots \cdots \cdots \cdots }$

${\displaystyle r_{n-4}=q_{n-4}r_{n-3}+r_{n-2}}$ con ${\displaystyle 0<r_{n-2}<r_{n-3}}$

${\displaystyle r_{n-3}=q_{n-3}r_{n-2}+r_{n-1}}$ con ${\displaystyle 0<r_{n-1}<r_{n-2}}$

${\displaystyle r_{n-2}=q_{n-2}r_{n-1}+1}$ .

L'ultimo resto è ${\displaystyle 1}$ in accordo con il fatto che ${\displaystyle a}$ e ${\displaystyle b}$ sono primi fra loro. Dobbiamo ora ottenere una rappresentazione di ${\displaystyle ax+by=1}$ tramite un processo che deriva dall'algoritmo. Iniziamo dal fondo e scriviamo ${\displaystyle 1}$ come combinazione lineare di ${\displaystyle r_{n-1}}$ e ${\displaystyle r_{n-2}}$

${\displaystyle 1=r_{n-2}-q_{n-2}r_{n-1}}$ .

La penultima equazione ${\displaystyle r_{n-3}=q_{n-3}r_{n-2}+r_{n-1}}$ è equivalente a

${\displaystyle r_{n-1}=r_{n-3}-q_{n-3}r_{n-2}}$ ,

e, sostituendo la penultima nell'ultima, otteniamo

${\displaystyle 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 ${\displaystyle 1}$ come combinazione lineare di ${\displaystyle r_{n-3}}$ e di ${\displaystyle r_{n-2}}$ .

Dalla terz'ultima equazione ${\displaystyle r_{n-4}=q_{n-4}r_{n-3}+r_{n-2}}$ abbiamo che

${\displaystyle r_{n-2}=r_{n-4}-q_{n-4}r_{n-3}}$

e, analogamente a quanto fatto in precedenza, otteniamo ${\displaystyle 1}$ come combinazione lineare di ${\displaystyle r_{n-4}}$ e di ${\displaystyle r_{n-3}}$ .

Il processo continua fino a quando si arriva ad avere ${\displaystyle 1}$ come combinazione lineare di ${\displaystyle r_{1}=a}$ e di ${\displaystyle r_{2}=b}$ . I coefficienti della combinazione lineare, che indichiamo con ${\displaystyle ~x_{0}~}$ e ${\displaystyle ~y_{0}~}$ , costituiscono una soluzione dell'equazione${\displaystyle ~ax+by=1~}$ .

Partiamo ora dall'uguaglianza che sappiamo essere vera ${\displaystyle ~ax_{0}+by_{0}=1~}$ e moltiplichiamo entrambi i membri per ${\displaystyle ~c~}$

${\displaystyle ~c(ax_{0}+by_{0})=c\cdot 1}$

${\displaystyle ~cax_{0}+cby_{0}=c~}$

${\displaystyle ~a(cx_{0})+b(cy_{0})=c~}$ .

Questo equivale a dire che la coppia ${\displaystyle ~(cx_{0},cy_{0})~}$ è soluzione dell'equazione ${\displaystyle ~ax+by=c~}$ .

La soluzione trovata non è l'unica soluzione dell'equazione ${\displaystyle ~ax+by=c~}$ . Infatti abbiamo

${\displaystyle ~ax+by=c~}$

${\displaystyle ~ax+by=a(cx_{0})+b(cy_{0})~}$

${\displaystyle ~a(x-cx_{0})=-b(y-cy_{0})~}$ .

Questa uguaglianza mostra che il prodotto ${\displaystyle ~a(x-cx_{0})~}$ è divisibile per ${\displaystyle ~b~}$ . Dal momento che ${\displaystyle ~a~}$ e ${\displaystyle ~b~}$ sono primi fra loro, possiamo concludere che ${\displaystyle ~(x-cx_{0})~}$ è divisibile per ${\displaystyle ~b~}$ , ovvero esiste un intero ${\displaystyle ~t~}$ tale che${\displaystyle ~x-cx_{0}=tb~}$ .Sostituendo questa relazione nella precedente otteniamo:

${\displaystyle ~a(x-cx_{0})=-b(y-cy_{0})~}$

${\displaystyle ~a(tb)=-b(y-cy_{0})~}$

ovvero ${\displaystyle ~y-cy_{0}=-ta~}$ .

In conclusione le soluzioni dell'equazione ${\displaystyle ~ax+by=c~}$ sono date da

${\displaystyle \left\{{\begin{matrix}x=cx_{0}+tb\\\\y=cy_{0}-ta\\\end{matrix}}\right.}$

con ${\displaystyle ~t~}$ intero.

Applichiamo il metodo descritto all'equazione ${\displaystyle ~8x+5y=81~}$ . Consideriamo quindi l'equazione ${\displaystyle ~8x+5y=1~}$ e implementiamo l'algoritmo di Euclide alla coppia ${\displaystyle ~8~}$ e ${\displaystyle ~5~}$ :

${\displaystyle 8~=~5\cdot 1+3}$

${\displaystyle 5~=~3\cdot 1+2}$

${\displaystyle 3~=~2\cdot 1+1\,.}$

Riscriviamo le tre uguaglianze mettendo in evidenza i resti

${\displaystyle 3~=~8-5\cdot 1}$

${\displaystyle 2~=~5-3\cdot 1}$

${\displaystyle 1~=~3-2\cdot 1\,.}$

Partiamo dall'ultima e sostituiamo a ritroso i valori:

${\displaystyle ~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 ${\displaystyle ~x=2~}$ e ${\displaystyle ~y=-3~}$ .

Una volta trovata una soluzione dell'equazione ${\displaystyle ~8x+5y=1~}$ , che indichiamo con ${\displaystyle ~(x_{0},y_{0})~}$ , per ottenere una soluzione dell'equazione ${\displaystyle ~8x+5y=81~}$ bastano tre moltiplicazioni per uno stesso fattore.

Moltiplicando per ${\displaystyle ~81~}$ i due membri di ${\displaystyle ~2\cdot 8-3\cdot 5=1~}$ , otteniamo che una soluzione dell'equazione ${\displaystyle ~8x+5y=81~}$ è data dalla coppia ${\displaystyle ~(2\cdot 81,-3\cdot 81)=(162,-243)~}$ .

La soluzione generale dell'equazione ${\displaystyle ~8x+5y=81~}$ è data da

${\displaystyle \left\{{\begin{matrix}x=162-5t\\\\y=-243+8t\,.\\\end{matrix}}\right.}$

Mostriamo ora come si possano usare le frazioni continue per risolvere l'equazione diofantea ${\displaystyle ~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${\displaystyle ~ax+by=c~}$ .

Impariamo dapprima a risolvere l'equazione ${\displaystyle ~ax-by=1~}$ con ${\displaystyle ~\mathrm {MCD} (a,b)=1~}$ .

Teorema

L'equazione ${\displaystyle ~ax-by=1~}$ , dove ${\displaystyle ~a~}$ e ${\displaystyle ~b~}$ sono interi positivi primi fra loro, ha infinite soluzioni intere ${\displaystyle ~(x,y)~}$ .

Dimostrazione

Trasformiamo dapprima ${\displaystyle {\frac {a}{b}}}$ in una frazione continua aritmetica limitata o semplice

${\displaystyle {\frac {a}{b}}=[\,a_{1};a_{2},\ldots ,a_{n-1},a_{n}\,]\,,}$

e calcoliamo le ridotte ${\displaystyle c_{1},c_{2},\ldots ,c_{n-1},c_{n}}$ .

Le ultime due

${\displaystyle 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

${\displaystyle ~p_{n}q_{n-1}-p_{n-1}q_{n}=(-1)^{n}~}$

e poiché ${\displaystyle ~p_{n}=a~}$ e ${\displaystyle ~q_{n}=b~}$ , si ha

${\displaystyle ~aq_{n-1}-bp_{n-1}=(-1)^{n}~}$ .

Se ${\displaystyle ~n~}$ è pari, cioè se abbiamo un numero pari di quozienti parziali${\displaystyle a_{1},a_{2},\ldots ,a_{n}}$ , ${\displaystyle ~(-1)^{n}=1~}$ e l'ultima equazione scritta diventa

${\displaystyle ~aq_{n-1}-bp_{n-1}=1~}$ .

Confrontando questa con l'equazione data ${\displaystyle ~ax-by=1~}$ , si vede che unasoluzione di questa è

${\displaystyle x_{0}=q_{n-1}\,,\ \ \ \ \ \ y_{0}=p_{n-1}}$ .

Questa, tuttavia, è una soluzione particolare e non la soluzionegenerale. Indicheremo le soluzioni particolari con ${\displaystyle ~(x_{0},y_{0})~}$ .D'altra parte se ${\displaystyle ~n~}$ è dispari così che ${\displaystyle ~(-1)^{n}=-1~}$ , possiamomodificare lo sviluppo

${\displaystyle {\frac {a}{b}}=[\,a_{1};a_{2},\ldots ,a_{n-1},a_{n}\,]}$

sostituendo

${\displaystyle {\frac {1}{a_{n}}}}$ con ${\displaystyle {\cfrac {1}{(a_{n}-1)+{\cfrac {1}{1}}}}}$ se ${\displaystyle ~a_{n}>1~}$

o sostituendo

${\displaystyle {\cfrac {1}{a_{n-1}+{\cfrac {1}{a_{n}}}}}}$ con ${\displaystyle {\cfrac {1}{a_{n-1}+1}}}$ se ${\displaystyle ~a_{n}=1~}$ .

Cioè, se lo sviluppo ha un numero dispari di quozienti parziali, sipuò trasformare in ${\displaystyle [\,a_{1};a_{2},\ldots ,a_{n-1},a_{n}-1,1\,]}$ se ${\displaystyle ~a_{n}>1~}$ o in ${\displaystyle [\,a_{1};a_{2},\ldots ,a_{n-1}+1\,]}$ se ${\displaystyle ~a_{n}=1~}$ ; in entrambi i casi il numero dei quozienti diviene pari.

Usando questa frazione continua, in entrambi i casi, ricalcoliamo${\displaystyle {\frac {p_{n-1}}{q_{n-1}}}}$ , ${\displaystyle {\frac {p_{n}}{q_{n}}}={\frac {a}{b}}}$ e l'equazione ${\displaystyle ~aq_{n-1}-bp_{n-1}=1~}$ è di nuovo soddisfatta.

Come già visto nella sezione precedente la soluzione generale è

${\displaystyle \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.)

Trovare le soluzioni intere dell'equazione indeterminata${\displaystyle ~205x-93y=1~}$ .

Qui gli interi ${\displaystyle ~205=5\cdot 41~}$ e ${\displaystyle ~93=3\cdot 31~}$ sono primi fra loroe l'equazione ha soluzioni intere. La frazione continua corrispondente a ${\displaystyle ~{\frac {205}{93}}~}$ cioè ${\displaystyle [\,2;4,1,8,2\,]}$ ha un numero dispari di quozienti parziali, ma può essere sostituita da${\displaystyle ~{\frac {205}{93}}=[\,2;4,1,8,1,1\,]~}$ , sviluppo equivalente con un numero paridi quozienti.Calcoliamone le ridotte.

${\displaystyle {\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 ${\displaystyle ~n=6~}$ , ${\displaystyle ~p_{n-1}=p_{5}=108=y_{0}~}$ , ${\displaystyle ~q_{n-1}=q_{5}=49=x_{0}~}$ , equindi, per la

${\displaystyle \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 è

${\displaystyle \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.}$

Il metodo per risolvere l'equazione${\displaystyle ~ax-by=-1~}$ con ${\displaystyle ~\mathrm {MCD} (a,b)=1~}$ è del tutto analogo a quello usato per risolvere l'equazione ${\displaystyle ~ax-by=+1~}$ con ${\displaystyle ~\mathrm {MCD} (a,b)=1~}$ .

Basta trasformare ${\displaystyle ~{\frac {a}{b}}~}$ in una frazione continua aritmetica limitatacon un numero dispari di ridotte.

Imparato a risolvere l'equazione${\displaystyle ~ax-by=1~}$ dove ${\displaystyle ~a~}$ e ${\displaystyle ~b~}$ sono interi primi fra loro, è facile risolverel'equazione${\displaystyle ~ax-by=c~}$ nella quale ${\displaystyle ~c~}$ è intero. Come abbiamo già visto nei paragrafi precedenti la soluzione generale di ${\displaystyle ~ax-by=c~}$ è

${\displaystyle \left\{{\begin{matrix}x=cx_{0}+bt&&\\&&t=0,\pm 1,\pm 2,\pm 3,\ldots \,.\\y=cy_{0}+at&&\end{matrix}}\right.}$

La discussione di questa equazione è simile, ad eccezione di alcune lievimodifiche, a quella dell'equazione ${\displaystyle ~ax-by=c~}$ . Sempre supponendo che${\displaystyle ~a~}$ e ${\displaystyle ~b~}$ siano interi positivi, troviamo dapprima una soluzioneparticolare dell'equazione${\displaystyle ~ax+by=c~}$ con ${\displaystyle ~\mathrm {MCD} (a,b)=1~}$ .

Per fare ciò, sviluppiamo ${\displaystyle ~{\frac {a}{b}}~}$ in frazione continua con unnumero pari di quozienti parziali.

Dalla tavola delle ridotteprendiamo ${\displaystyle ~p_{n-1}~}$ e ${\displaystyle ~q_{n-1}~}$ . Allora vale${\displaystyle ~aq_{n-1}-bp_{n-1}=1~}$ ,come in precedenza.

L'artificio consiste ora nello scrivere l'equazione data nella forma

${\displaystyle ~ax+by=c\cdot 1=c(aq_{n-1}-bp_{n-1})~}$ .

Cambiamo l'ordine dei termini ed otteniamo

${\displaystyle ~a(cq_{n-1}-x)=b(y+cp_{n-1})~}$ .

Quindi ${\displaystyle ~b~}$ divide la quantità che figura a sinistra; ma ${\displaystyle ~\mathrm {MCD} (a,b)=1~}$ e quindi ${\displaystyle ~b~}$ , che non ha divisori comuni con ${\displaystyle ~a~}$ (salvo ${\displaystyle ~1~}$ ), deve dividere ${\displaystyle ~cq_{n-1}-x~}$ che equivale a dire che esiste un intero ${\displaystyle ~t~}$ tale che

${\displaystyle ~cq_{n-1}-x=tb~}$

o anche che

${\displaystyle ~x=cq_{n-1}-tb~}$ .

Sostituendo si ottiene

${\displaystyle ~a(tb)=b(y+cp_{n-1})~}$

la quale, risolta nella variabile ${\displaystyle ~y~}$ , dà

${\displaystyle ~y=at-cp_{n-1}~}$ .

Viceversa, qualunque sia l'intero ${\displaystyle ~t~}$ , sostituendo in ${\displaystyle ~ax+by~}$ si ha

${\displaystyle ~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 ${\displaystyle ~ax+by=c~}$ è soddisfatta.

Quindi la sua soluzione generale è

${\displaystyle \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.}$

Risolviamo ora con le frazioni continue l'equazione diofantea ${\displaystyle ~8x+5y=81~}$ . Sviluppiamo ${\displaystyle ~{\frac {8}{5}}~}$ in frazione continua, ottenendo${\displaystyle ~{\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${\displaystyle ~{\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:${\displaystyle ~1\,,2\,,{\frac {3}{2}}\,,{\frac {8}{5}}~}$ .

In conclusione la soluzione generale dell'equazione diofantea ${\displaystyle ~8x+5y=81~}$ è data da

${\displaystyle \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.}$ .

• (EN) Eric W. Weisstein, Diophantine Equation, in MathWorld, Wolfram Research.
• S. M. Voronin: Diophantine equations Articolo in Encyclopaedia of Mathematics

• Equazione diofantea
• Algoritmo di Euclide
• Massimo comun divisore
• Equazione
• Diofanto di Alessandria
• Frazione continua

• Wikimedia Commons contiene immagini o altri file sull'Equazione diofantea lineare

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica