Equazione diofantea lineare

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

Un'equazione diofantea lineare è un'equazione diofantea in cui le relazioni tra le variabili sono di tipo lineare.

Equazione diofantea lineare in due variabili[modifica | modifica wikitesto]

Criterio di risolubilità[modifica | modifica wikitesto]

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 coprimi[modifica | modifica wikitesto]

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 Euclide[modifica | modifica wikitesto]

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.

Esempio[modifica | modifica wikitesto]

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 continue[modifica | modifica wikitesto]

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=±1[modifica | modifica wikitesto]

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

Esempio[modifica | modifica wikitesto]

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 è

Osservazione[modifica | modifica wikitesto]

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)=1[modifica | modifica wikitesto]

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)=1[modifica | modifica wikitesto]

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 è

Esempio[modifica | modifica wikitesto]

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

.

Riferimenti[modifica | modifica wikitesto]

Voci correlate[modifica | modifica wikitesto]

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