Rezolvarea ecuațiilor diofantice

Orice congruenta ax1+c?0 (mod b) se poate scrie ca o ecuatie ax1+bx2+c=0 (in care a? 0), b?1 si c, x1, x2 sunt numere intregi. Daca a, b, c sunt numere intregi date si x1 si x2 sunt considerate necunoscute, problema se reduce la gasirea solutiilor intregi ale unei ecuatii liniare cu coeficienti intregi. Daca f(x1,..., xn) este un polinom in x1,..., xn cu coeficienti intregi, atunci ecuatia f(x1,..., xn) = A se numeste diofantica daca solutiile ei sunt numere intregi. Denumirea acestor ecuatii deriva de la numele matematicianului grec Diofantos din Alexandria. Daca o astfel de ecuatie admite solutii, atunci ea admite o infinitate de n-upluri care o satisfac.

In continuare se va trata cazul n=2: ax+by=c

Daca a si b sunt numere prime intre ele si x0, y0 constituie o solutie pentru ax+by=c, atunci totalitatea solutiilor se poate reprezenta sub forma: x= x0+bt, y= y0 -at, unde t este un numar intreg oarecare. O solutie a ecuatiei se poate obtine cu ajutorul penultimei fractii de aproximare pentru reprezentarea sub forma de fractie continua a lui a/b. Considerand ca penultima fractie este m/n, x0=nc, y0=-mc.

Exemplu:

Fie ecuatia: 43x+19y=2.

Fractiile de aproximare ale lui 43/19 sunt: 7/3, 9/4, 43/19.

Din fractia 9/4 se obtine x0=4*2=8, y0=-9*2=-18. Astfel, solutia generala se poate scrie de forma: x=8+19t si y=-18-43t, unde t este un numar oarecare.

Implementare

Algoritmul de mai sus este valabil, dupa cum am precizat, in cazul cand cele 2 numere a si b sunt prime intre ele. Daca dorim rezolvarea unei ecuatii in care cele 2 numere nu sunt neaparat prime intre ele, se poate proceda in felul urmator: se calculeaza cel mai mare divizor comun al lor (sigur este diferit de 1), iar apoi se evalueaza daca ecuatie poate sau nu avea solutii, in functie de valoarea lui c. Daca c este divizibil cu cmmdc-ul celor 2 numere, atunci se simplifica intreaga ecuatie cu cmmdc si problema se reduce la cea prezentata mai sus. Daca c nu se imparte exact la cmmdc, atunci putem spune ca ecuatia nu are solutii intregi.