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
,
,
numeri interi.
L'equazione
ha soluzioni intere se e solo se
è divisibile per il massimo comun divisore di
e
, cioè se e solo se
.
Dimostrazione
Sia
e ricordiamo che l'identità di Bézout afferma che esistono due numeri interi
e
tali che
.
Supponiamo che
divida
. Moltiplichiamo entrambi i membri dell'equazione per il numero intero
ed otteniamo
![{\displaystyle a\left({\frac {c}{d}}\,x_{0}\right)+b\left({\frac {c}{d}}\,y_{0}\right)={\frac {c}{d}}\,d=c;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8b9f1199fa331412ae72efa685033cb60b987b6)
se ne conclude che la coppia
è soluzione dell'equazione diofantea.
Supponiamo viceversa che l'equazione possegga una soluzione data dalla coppia
. L'espressione
è una combinazione lineare di interi divisibili per
e quindi fornisce un intero, uguale a
, divisibile per tale intero. (c.v.d.)
Ogni equazione diofantea risolubile, che scriviamo
, si può ridurre ad un'equazione diofantea della forma
avente i coefficienti coprimi.
Abbiamo infatti che, se poniamo:
otteniamo
![{\displaystyle (d{\tilde {a}})x+(d{\tilde {b}})y=c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0b10e10fbdd734347ab799616db7a1c68bcac72a)
![{\displaystyle d({\tilde {a}}x+{\tilde {b}}y)=c}](https://wikimedia.org/api/rest_v1/media/math/render/svg/338b87201ccb07f4f3c5c5292c522a3c145a2047)
![{\displaystyle {\tilde {a}}x+{\tilde {b}}y={\frac {c}{d}}=:{\tilde {c}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b8c49e15ef2f5a3218fb7551b06e6f20010c97d)
in cui
.
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"
con
, occupiamoci della risoluzione dell'equazione "particolare"
.
Possiamo supporre che
sia maggiore di
e implementiamo l'algoritmo di Euclide. Poniamo
e
:
con ![{\displaystyle 0<r_{3}<r_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/02c90c5eeee770dc800b756f0296da3db38a632c)
con ![{\displaystyle 0<r_{4}<r_{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d3ee3fb49b5c972670f922a195bbe2d21ef417e)
con ![{\displaystyle 0<r_{n-2}<r_{n-3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8c9c66e0b579ea30801ea01b843df6bcd95479e)
con ![{\displaystyle 0<r_{n-1}<r_{n-2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6f3220a401532d01b6e87ff1ddec38cd5c5690d5)
.
L'ultimo resto è
in accordo con il fatto che
e
sono primi fra loro. Dobbiamo ora ottenere una rappresentazione di
tramite un processo che deriva dall'algoritmo. Iniziamo dal fondo e scriviamo
come combinazione lineare di
e
.
La penultima equazione
è equivalente a
,
e, sostituendo la penultima nell'ultima, otteniamo
.
Abbiamo così ottenuto
come combinazione lineare di
e di
.
Dalla terz'ultima equazione
abbiamo che
![{\displaystyle r_{n-2}=r_{n-4}-q_{n-4}r_{n-3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce57f6acda8ea09da0c5df3f2f112e1d185b9a44)
e, analogamente a quanto fatto in precedenza, otteniamo
come combinazione lineare di
e di
.
Il processo continua fino a quando si arriva ad avere
come combinazione lineare di
e di
. I coefficienti della combinazione lineare, che indichiamo con
e
, costituiscono una soluzione dell'equazione
.
Partiamo ora dall'uguaglianza che sappiamo essere vera
e moltiplichiamo entrambi i membri per
.
Questo equivale a dire che la coppia
è soluzione dell'equazione
.
La soluzione trovata non è l'unica soluzione dell'equazione
. Infatti abbiamo
.
Questa uguaglianza mostra che il prodotto
è divisibile per
. Dal momento che
e
sono primi fra loro, possiamo concludere che
è divisibile per
, ovvero esiste un intero
tale che
. Sostituendo questa relazione nella precedente otteniamo:
ovvero
.
In conclusione le soluzioni dell'equazione
sono date da
con
intero.
Applichiamo il metodo descritto all'equazione
. Consideriamo quindi l'equazione
e implementiamo l'algoritmo di Euclide alla coppia
e
:
Riscriviamo le tre uguaglianze mettendo in evidenza i resti
Partiamo dall'ultima e sostituiamo a ritroso i valori:
.
Quindi abbiamo
e
.
Una volta trovata una soluzione dell'equazione
, che indichiamo con
, per ottenere una soluzione dell'equazione
bastano tre moltiplicazioni per uno stesso fattore.
Moltiplicando per
i due membri di
, otteniamo che una soluzione dell'equazione
è data dalla coppia
.
La soluzione generale dell'equazione
è data da
Mostriamo ora come si possano usare le frazioni continue per risolvere l'equazione diofantea
. 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
.
Impariamo dapprima a risolvere l'equazione
con
.
Teorema
L'equazione
, dove
e
sono interi positivi primi fra loro, ha infinite soluzioni intere
.
Dimostrazione
Trasformiamo dapprima
in una frazione continua aritmetica limitata o semplice
e calcoliamo le ridotte
.
Le ultime due
sono la chiave della soluzione. Queste infatti soddisfano la relazione fondamentale
e poiché
e
, si ha
.
Se
è pari, cioè se abbiamo un numero pari di quozienti parziali
,
e l'ultima equazione scritta diventa
.
Confrontando questa con l'equazione data
, si vede che una soluzione di questa è
.
Questa, tuttavia, è una soluzione particolare e non la soluzione generale. Indicheremo le soluzioni particolari con
. D'altra parte se
è dispari così che
, possiamo modificare lo sviluppo
sostituendo
con
se
o sostituendo
con
se
.
Cioè, se lo sviluppo ha un numero dispari di quozienti parziali, si può trasformare in
se
o in
se
; in entrambi i casi il numero dei quozienti diviene pari.
Usando questa frazione continua, in entrambi i casi, ricalcoliamo
,
e l'equazione
è di nuovo soddisfatta.
Come già visto nella sezione precedente la soluzione generale è
(c.v.d.)
Trovare le soluzioni intere dell'equazione indeterminata
.
Qui gli interi
e
sono primi fra loro e l'equazione ha soluzioni intere. La frazione continua corrispondente a
cioè
ha un numero dispari di quozienti parziali, ma può essere sostituita da
, sviluppo equivalente con un numero pari di quozienti. Calcoliamone le ridotte.
Qui
,
,
, e quindi, per la
,
la soluzione generale dell'equazione è
Il metodo per risolvere l'equazione
con
è del tutto analogo a quello usato per risolvere l'equazione
con
.
Basta trasformare
in una frazione continua aritmetica limitata con un numero dispari di ridotte.
Imparato a risolvere l'equazione
dove
e
sono interi primi fra loro, è facile risolvere l'equazione
nella quale
è intero. Come abbiamo già visto nei paragrafi precedenti la soluzione generale di
è
La discussione di questa equazione è simile, ad eccezione di alcune lievi modifiche, a quella dell'equazione
. Sempre supponendo che
e
siano interi positivi, troviamo dapprima una soluzione particolare dell'equazione
con
.
Per fare ciò, sviluppiamo
in frazione continua con un numero pari di quozienti parziali.
Dalla tavola delle ridotte prendiamo
e
. Allora vale
, come in precedenza.
L'artificio consiste ora nello scrivere l'equazione data nella forma
.
Cambiamo l'ordine dei termini ed otteniamo
.
Quindi
divide la quantità che figura a sinistra; ma
e quindi
, che non ha divisori comuni con
(salvo
), deve dividere
che equivale a dire che esiste un intero
tale che
o anche che
.
Sostituendo si ottiene
la quale, risolta nella variabile
, dà
.
Viceversa, qualunque sia l'intero
, sostituendo in
si ha
e l'equazione
è soddisfatta.
Quindi la sua soluzione generale è
Risolviamo ora con le frazioni continue l'equazione diofantea
. Sviluppiamo
in frazione continua, ottenendo
Quindi
. La frazione ha un numero pari di coefficienti parziali, quindi non dobbiamo modificarla. Le ridotte della frazione continua sono:
.
In conclusione la soluzione generale dell'equazione diofantea
è data da
.