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 variabiliModifica

Criterio di risolubilitàModifica

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

 

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.)

Riducibilità ai coefficienti coprimiModifica

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

 
 
 

in cui  .

Risoluzione con l'algoritmo di EuclideModifica

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  
  con  

 

  con  
  con  

 .

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

 

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.

EsempioModifica

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

 

Risoluzione con le frazioni continueModifica

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  .

L'equazione indeterminata ax-by=±1Modifica

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.)

EsempioModifica

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 è

 

OsservazioneModifica

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.

La soluzione generale di ax-by=c con MCD(a,b)=1Modifica

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 soluzione generale di ax+by=c con MCD(a,b)=1Modifica

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 è

 

EsempioModifica

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

 .

RiferimentiModifica

Voci correlateModifica

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