Rezolvarea ecuaiilor diofanticeOrice congruen ax1+c?0 (mod b) se poate scrie ca o ecuaie ax1+bx2+c=0 (n care a? 0), b?1 i c, x1, x2 sunt numere ntregi. Dac a, b, c sunt numere ntregi date i x1 i x2 sunt considerate necunoscute, problema se reduce la gsirea soluiilor ntregi ale unei ecuaii liniare cu coeficieni ntregi. Daca f(x1,, xn) este un polinom n x1,, xn cu coeficieni ntregi, atunci ecuaia f(x1,, xn) = A se numete diofantic dac soluiile ei sunt numere ntregi. Denumirea acestor ecuaii deriv de la numele matematicianului grec Diofantos din Alexandria. Dac o astfel de ecuaie admite soluii, atunci ea admite o infinitate de n-upluri care o satisfac.n continuare se va trata cazul n=2: ax+by=cDac a i b sunt numere prime ntre ele i x0, y0 constituie o soluie pentru ax+by=c, atunci totalitatea soluiilor se poate reprezenta sub forma: x=x0+bt, y=y0 at, unde t este un numr ntreg oarecare. O soluie a ecuaiei se poate obine cu ajutorul penultimei fracii de aproximare pentru reprezentarea sub form de fracie continu a lui a/b. Considernd c penultima fracie este m/n, x0=nc, y0=-mc.Exemplu:Fie ecuaia: 43x+19y=2.Fraciile de aproximare ale lui 43/19 sunt: 7/3, 9/4, 43/19.Din fracia 9/4 se obine x0=4*2=8, y0=-9*2=-18. Astfel, soluia general se poate scrie de forma: x=8+19t i y=-18-43t, unde t este un numr oarecare.ImplementareAlgoritmul de mai sus este valabil, dup cum am precizat, n cazul cnd cele 2 numere a i b sunt prime ntre ele. Dac dorim rezolvarea unei ecuaii n care cele 2 numere nu sunt neaprat prime ntre ele, se poate proceda n felul urmtor: se calculeaz cel mai mare divizor comun al lor (sigur este diferit de 1), iar apoi se evalueaz dac ecuaie poate sau nu avea soluii, n funcie de valoarea lui c. Dac c este divizibil cu cmmdc-ul celor 2 numere, atunci se simplific ntreaga ecuaie cu cmmdc i problema se reduce la cea prezentat mai sus. Dac c nu se mparte exact la cmmdc, atunci putem spune c ecuaia nu are soluii ntregi.Pe lng aceasta, intervin o serie de cazuri critice n care algoritmul de mai sus nu poate fi aplicat, cum ar fi de exemplu cazurile n care nu exist penultima fracie. Dar se poate calcula soluia i n aceste cazuri:a=0, b=0n acest caz soluia depinde valoarea lui c:c=0 => x i y poate fi orice numr ntregc ? 0=> nu exist soluiia=0, b? 0Ecuaia devine: by=c. Deci y se poate calcula, innd ns cont c vorbim numai de numere ntregi.a?0, b= 0Analog cu cazul anterior.Dac unul dintre numerele a sau b are valoarea 1 nu se mai poate vorbi de penultima fracie de aproximare, deci i aceste cazuri trebuie tratate separat.O alt observaie este aceea c fracia de aproximare (m/n) aproximeaz fracia (a/b) n plus sau n minus. De aceea n la sfrit trebuie s corectez rezultatul n funcie de aceasta, innd seama i de semnul fraciei a/b.Sursa programului#include #include #include long int v[100];//obtine penultima fractie de aproximarevoid get_mn(long int &a,long int &b,int k){ if (k>0) { long int aux=v[k-1]*b+a; a=b;b=aux; get_mn(a,b,k-1); } else a=a+b-(b=a);}long int _cmmdc(long int a,long int b){ while (a!=b) if (a>b) a-=b; else b-=a; return a;}void stop(){ printf("Nu exista solutii...\\\\\\\\
");}int solutii(long int a,long int b,long int c, long int &x0,long int &n1,long int &y0,long int &n2){ long int m,n,cmmdc=1,_a,_b; int nr=-1; _a=labs(a);_b=labs(b); if ((_a>1)&&(_b>1)) cmmdc=_cmmdc(_a,_b); if (cmmdc!=1){ if (c%cmmdc) {stop();return 0;} else a/=cmmdc,b/=cmmdc,c/=cmmdc; } m=a;n=b; if (!(a*b)) if (!a) if (!b) { //0=c if (!c) printf("x,y?Z\\\\\\\\
"); else stop(); return 0; } else { // by=c if (c%b) stop(); else { printf("x?Z\\\\\\\\
"); printf("y=%ld\\\\\\\\
",c/b); } return 0; } else { //ax=c if (c%a) stop(); else {printf("x=%ld\\\\\\\\
",c/a); printf("y?Z\\\\\\\\
"); } return 0; } if (labs(m)==1) { // inseamna ca este de forma ?x+b*y=c, deci nu exista // penultima fractie de aproximare x0=c*m;n1=-b*m; y0=0;n2=1; return 1; } else if (labs(n)==1) { // inseamna ca este de forma a*x?y=c, deci nu exista // penultima fractie de aproximare x0=0;n1=1; y0=c*n;n2=-a*n; return 1; } // m si n sunt diferite de 1, si diferite intre ele m=labs(m);n=labs(n); while (m!=1){ if (m>n){ v[++nr]=m/n; m-=m/n*n; } else if (m0) if (_a*n<_b*m) c=-c; if (a*b<0) if (_a*n>_b*m) c=-c; if (a<0) m=-m; if (b<0) n=-n; x0=n*c;n1=b; y0=-m*c;n2=-a; return 1;}void main(void){ long int a,b,c,x0,y0,n1,n2; do{ clrscr(); puts("Se rezolva ecuatia: ax+by=c, a,b,x,y,cZ"); printf("a=");scanf("%ld",&a);fflush(stdin); printf("b=");scanf("%ld",&b);fflush(stdin); printf("c=");scanf("%ld",&c);fflush(stdin); printf("----------------------------------------\\\\\\\\
"); if (solutii(a,b,c,x0,n1,y0,n2)){ if (!x0) if (labs(n1)!=1) printf("x=%ldt\\\\\\\\
",n1); else printf("x=%st\\\\\\\\
",n1<0?"-":""); else if (labs(n1)!=1) printf("x=%ld%+ldt\\\\\\\\
",x0,n1); else printf("x=%ld%st\\\\\\\\
",x0,n1<0?"-":""); if (!y0) if (labs(n2)!=1) printf("y=%ldt\\\\\\\\
",n2); else printf("y=%st\\\\\\\\
",n2<0?"-":""); else if (labs(n2)!=1) printf("y=%ld%+ldt\\\\\\\\
",y0,n2); else printf("y=%ld%st\\\\\\\\
",y0,n2<0?"-":""); printf("unde t este un numar intreg\\\\\\\\
");} puts("Apasati o tasta (x pentru a termina)..."); c=getch(); }while (c!='x');