Equazione diofantea lineare

Template:F 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 $\mathrm{MCD}(a,b)\mid c$.

Dimostrazione

Sia $d:=\mathrm{MCD}(a,b)$ e ricordiamo che l'identità di Bézout afferma che esistono due numeri interi $x_0$ e $y_0$ tali che

$a{x}_0+b{y}_0=d$.

Supponiamo che $d$ divida $c$. Moltiplichiamo entrambi i membri dell'equazione per il numero intero $\frac{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 $(\frac{c}{d}{x}_0,\frac{c}{d}{y}_0)$ è soluzione dell'equazione diofantea.

Supponiamo viceversa che l'equazione possegga una soluzione data dalla coppia $(x_1,y_1)$. L'espressione $a{x}_1+b{y}_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:=\mathrm{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 $\mathrm{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 $\mathrm{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 $a{x}_0+b{y}_0=1$ e moltiplichiamo entrambi i membri per $c$

$c(a{x}_0+b{y}_0)=c\cdot 1$

$ca{x}_0+cb{y}_0=c$

$a(c{x}_0)+b(c{y}_0)=c$.

Questo equivale a dire che la coppia $(c{x}_0,c{y}_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(c{x}_0)+b(c{y}_0)$

$a(x-c{x}_0)=-b(y-c{y}_0)$.

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

$a(x-c{x}_0)=-b(y-c{y}_0)$

$a(tb)=-b(y-c{y}_0)$

ovvero $y-c{y}_0=-ta$.

In conclusione le soluzioni dell'equazione $ax+by=c$ sono date da

$\{\begin{array}{c}x=c{x}_0+tb\\ \\ y=c{y}_0-ta\end{array}$

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

$\{\begin{array}{c}x=162-5t\\ \\ y=-243+8t.\end{array}$

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{M}\mathrm{C}\mathrm{D}(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,\dots ,a_{n-1},a_n],$

e calcoliamo le ridotte $c_1,c_2,\dots ,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

$a{q}_{n-1}-b{p}_{n-1}=(-1{)}^n$.

Se $n$ è pari, cioè se abbiamo un numero pari di quozienti parziali $a_1,a_2,\dots ,a_n$, $(-1{)}^n=1$ e l'ultima equazione scritta diventa

$a{q}_{n-1}-b{p}_{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,\dots ,a_{n-1},a_n]$

sostituendo

$\frac{1}{a_n}$ con $\frac{1}{(a_n-1)+\frac{1}{1}}$ se $a_n>1$

o sostituendo

$\frac{1}{a_{n-1}+\frac{1}{a_n}}$ con $\frac{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,\dots ,a_{n-1},a_n-1,1]$ se $a_n>1$ o in $[a_1;a_2,\dots ,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 $a{q}_{n-1}-b{p}_{n-1}=1$ è di nuovo soddisfatta.

Come già visto nella sezione precedente la soluzione generale è

$\{\begin{array}{ccc}x=x_0+tb& & \\ & & t=0,\pm 1,\pm 2,\pm 3,\dots .\\ y=y_0+ta& & \end{array}$ (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{array}{ccccccccc}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& & & \frac{2}{1}& \frac{9}{4}& \frac{11}{5}& \frac{97}{44}& \frac{108}{49}& \frac{205}{93}\end{array}$

Qui $n=6$, $p_{n-1}=p_5=108=y_0$, $q_{n-1}=q_5=49=x_0$, e quindi, per la

$\{\begin{array}{ccc}x=x_0+tb& & \\ & & t=0,\pm 1,\pm 2,\pm 3,\dots .\\ y=y_0+ta& & \end{array}$,

la soluzione generale dell'equazione è

$\{\begin{array}{ccc}x=x_0+tb=49+93t& & \\ & & t=0,\pm 1,\pm 2,\pm 3,\dots .\\ y=y_0+ta=108+205t& & \end{array}$

Osservazione

Il metodo per risolvere l'equazione $ax-by=-1$ con $\mathrm{M}\mathrm{C}\mathrm{D}(a,b)=1$ è del tutto analogo a quello usato per risolvere l'equazione $ax-by=+1$ con $\mathrm{M}\mathrm{C}\mathrm{D}(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$ è

$\{\begin{array}{ccc}x=c{x}_0+bt& & \\ & & t=0,\pm 1,\pm 2,\pm 3,\dots .\\ y=c{y}_0+at& & \end{array}$

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{M}\mathrm{C}\mathrm{D}(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 $a{q}_{n-1}-b{p}_{n-1}=1$, come in precedenza.

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

$ax+by=c\cdot 1=c(a{q}_{n-1}-b{p}_{n-1})$.

Cambiamo l'ordine dei termini ed otteniamo

$a(c{q}_{n-1}-x)=b(y+c{p}_{n-1})$.

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

$c{q}_{n-1}-x=tb$

o anche che

$x=c{q}_{n-1}-tb$.

Sostituendo si ottiene

$a(tb)=b(y+c{p}_{n-1})$

la quale, risolta nella variabile $y$, dà

$y=at-c{p}_{n-1}$.

Viceversa, qualunque sia l'intero $t$, sostituendo in $ax+by$ si ha

$ax+by=a(c{q}_{n-1}-tb)+b(at-c{p}_{n-1})=c(a{q}_{n-1}-b{p}_{n-1})=c\cdot 1=c$

e l'equazione $ax+by=c$ è soddisfatta.

Quindi la sua soluzione generale è

$\{\begin{array}{ccc}x=c{q}_{n-1}-tb& & \\ & & t=0,\pm 1,\pm 2,\pm 3,\dots .\\ y=-c{p}_{n-1}+at& & \end{array}$

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+\frac{1}{\frac{5}{3}}=1+\frac{1}{1+\frac{2}{3}}=1+\frac{1}{1+\frac{1}{\frac{3}{2}}}=1+\frac{1}{1+\frac{1}{1+\frac{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

$\{\begin{array}{ccc}x=81\cdot 2-5t=162-5t& & \\ & & t=0,\pm 1,\pm 2,\pm 3,\dots .\\ y=-81\cdot 3+8t=-243+8t& & \end{array}$.

Bibliografia

• Template:MathWorld
• S. M. Voronin: Diophantine equations Articolo in Encyclopaedia of Mathematics

Voci correlate

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