Equações Diofantinas - Problema

To resolvendo um problema de computação, e necessito saber como resolveria esse tipo de equação diofantina:
Nx - My = Z
Exemplos:
7x - 5y = 3
22x - 15y = 14

Eu necessito saber a menor combinação possivel, de tal forma que o menor entre Nx e My sejam minimo.

OBS: Sempre vai ser possivel resolver a equação.

tomemos o primeiro exemplo.

7x - 5y = 3

a = 7
b = -5
c = 3
A primeira coisa a fazer, para saber se tem solução, é tirar o mdc entre a e b. Se esse mdc dividir "c", entao sabemos que a equação tem solução.

Entao, na equação temos:
7x - 5y = 3

mdc(5,7) = 1 , e 1 divide 3. entao essa equação tem solução.

Entao, atribuimos, arbitrariamente valores para x e y, a fim de achar uma das soluções.
Na equação, vemos facilmente que satifaz a igualdade quando x = 4 e y = 5.

esses valores, chamaremos de x0 e y0.

Então, partimos para a fórmula.

X = x0 + (b/d).t

X = 4 + (-5/1).t
X = 4 - 5.t


Y = y0 - (a/d).t

Y = 5 - (7/1).t
Y = 5 - 7.t


t é um número arbitrário, que sempre satisfará a equação. para verificar usemos t = 2

X = 4 - 5.2
X = 4 - 10
X = -6

Y = 5 - 7.2
Y = 5 - 14
Y = -9

Substituindo na equação original temos:

7x - 5y = 3
7(-6) - 5(-9) = 3
- 42 + 45 = 3 Igualdade correta

Uma solução algébrica

7x - 5y = 3 ----> y = (7x - 3)/5 ----> y = x + (2x - 3)/5 ----> Fazendo s = (2x - 3)/5 ---->

x = (5s + 3)/2 ----> x = 2s + 1 + (s + 1)/2 ----> Fazendo (s + 1)/2 = t ----> s = 2t - 1

x = [5*(2t - 1) + 3]/2 ----> x = 5t - 1

y = [7*(5t - 1) - 3]/5 ----> y = 7t - 2

Agora basta variar t

Por exemplo, para t = 1 ----> x = 4 ----> y = 5 ----> Exatamente o exemplo inicial do Ramon