Equazione diofantea lineare
Da Wikipedia, l'enciclopedia libera.
Un'equazione diofantea lineare è un'equazione diofantea in cui le relazioni tra le variabili sono di tipo lineare.
[modifica] Equazione diofantea lineare in due variabili
Siano a, b, c interi. L'equazione
ax + by = c
ha soluzioni intere se e solo se c è divisibile per il massimo comun divisore di a e b
MCD(a,b) | c
cosa che si può vedere raccogliendo MCD(a,b) al primo membro.
Per risolvere una diofantea, basta dividere, con l'algoritmo euclideo, a per b se a>b, altrimenti si divide b per a, fino ad ottenere resto uguale a MCD(a,b), poi si risale dal basso verso l'alto.
[modifica] Esempio
12x + 7y = 3
si ha
12 = 7 + 5 resto 5 ;
7 = 5 + 2 resto 2 ;
5 = 2*2 + 1 resto 1 ;
in ognuna delle tre uguaglianze ricaviamo i resti:
5 = 12 - 7
2= 7 - 5
1 = 5 - 2*2
risalendo: 1 = 5 - 2*2 = 12 - 7 - 2*(7-5)= 12 - 7 - 2*(7-(12-7)) ;
allora: 1 = 12 - 7 - 4*7 + 2*12 ;
raccolti 7 e 12 si ha: 1 = 12*3 - 7*5 ;
ora moltiplicando per 3 viene: 3 = 12*9 - 7*15 ;
quindi una coppia (x,y) di soluzioni è (9;-15).
Tutte le altre si ottengono tenendo conto che se (X,Y) risolvono la ax + by = c allora anche (X + kb,Y − ka) la risolvono per ogni k intero.
Nel nostro esempio le soluzioni sono le coppie ordinate (9 + 7k; − 15 − 12k).
