Equazione diofantea lineare

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

Un'equazione diofantea lineare è un'equazione diofantea in cui le relazioni tra le variabili sono di tipo 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 una soluzione di questa è

${\displaystyle 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 ${\displaystyle ~(x_{0},y_{0})~}$. D'altra parte se ${\displaystyle ~n~}$ è dispari così che ${\displaystyle ~(-1)^{n}=-1~}$, possiamo modificare 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, si può 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 loro e 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 pari di 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}~}$, e quindi, 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 limitata con 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 risolvere l'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 lievi modifiche, a quella dell'equazione ${\displaystyle ~ax-by=c~}$. Sempre supponendo che ${\displaystyle ~a~}$ e ${\displaystyle ~b~}$ siano interi positivi, troviamo dapprima una soluzione particolare 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 un numero pari di quozienti parziali.

Dalla tavola delle ridotte prendiamo ${\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 Teknopedia che trattano di matematica