Orice congruenta ax1+c0 (mod b) se poate scrie ca o ecuatie ax1+bx2+c=0 (in care a 0), b1 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.
Pe langa aceasta, intervin o serie de cazuri critice in care algoritmul de mai sus nu poate fi aplicat, cum ar fi de exemplu cazurile in care nu exista penultima fractie. Dar se poate calcula solutia si in aceste cazuri:
. a=0, b=0
In acest caz solutia depinde valoarea lui c:
. c=0 => x si y poate fi orice numar intreg
. c 0 => nu exista solutii
. a=0, b 0
Ecuatia devine: by=c. Deci y se poate calcula, tinand insa cont ca vorbim numai de numere intregi.
. a0, b= 0
Analog cu cazul anterior.
Daca unul dintre numerele a sau b are valoarea 1 nu se mai poate vorbi de penultima fractie de aproximare, deci si aceste cazuri trebuie tratate separat.
O alta observatie este aceea ca fractia de aproximare (m/n) aproximeaza fractia (a/b) in plus sau in minus. De aceea in la sfarsit trebuie sa corectez rezultatul in functie de aceasta, tinand seama si de semnul fractiei a/b.
Sursa programului
