Rezolvarea ecuatiilor diofantice
of 5
Transcript of Rezolvarea ecuatiilor diofantice
-
8/14/2019 Rezolvarea ecuatiilor diofantice
1/5
4
11
13
12
4
5
13
12
5
43
12
5
19
12
19
52
19
43
+
+
+=
+
+=
+
+=+=+=
Rezolvarea ecuaiilor diofantice
Orice congruen ax1+c0 (mod b) se poate scrie ca o ecuaieax1+bx2+c=0 (n care a 0), b1 i c, x1, x2 sunt numere ntregi. Dac a,
b, c sunt numere ntregi date i x1 i x2 sunt consideratenecunoscute, problema se reduce la gsirea soluiilor ntregi aleunei ecuaii liniare cu coeficieni ntregi. Daca f(x1 ,, xn) este unpolinom n x1,, xn cu coeficieni ntregi, atunci ecuaia f(x1,, xn) = Ase numete diofantic dac soluiile ei sunt numere ntregi.Denumirea acestor ecuaii deriv de la numele matematicianuluigrec Diofantos din Alexandria. Dac o astfel de ecuaie admitesoluii, atunci ea admite o infinitate de n-upluri care o satisfac.
n continuare se va trata cazul n=2: ax+by=c
Dac a i b sunt numere prime ntre ele i x0,y0 constituie o soluiepentru ax+by=c, atunci totalitatea soluiilor se poate reprezenta subforma: x= x0+bt, y= y0 at, unde t este un numr ntreg oarecare. Osoluie a ecuaiei se poate obine cu ajutorul penultimei fracii deaproximare pentru reprezentarea sub form de fracie continu alui 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 obinex0=4*2=8, y0=-9*2=-18. Astfel, soluia
general se poate scrie de forma:x=8+19t i y=-18-43t, unde teste un numr oarecare.
Implementare
Algoritmul de mai sus este valabil, dup cum am precizat, n cazulcnd cele 2 numere a i b sunt prime ntre ele. Dac dorimrezolvarea unei ecuaii n care cele 2 numere nu sunt neapratprime ntre ele, se poate proceda n felul urmtor: se calculeazcel mai mare divizor comun al lor (sigur este diferit de 1), iar apoise evalueaz dac ecuaie poate sau nu avea soluii, n funcie devaloarea lui c. Dac c este divizibil cu cmmdc-ul celor 2 numere,
-
8/14/2019 Rezolvarea ecuatiilor diofantice
2/5
atunci se simplific ntreaga ecuaie cu cmmdc i problema sereduce la cea prezentat mai sus. Dac c nu se mparte exact lacmmdc, 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 exemplucazurile n care nu exist penultima fracie. Dar se poate calculasoluia i n aceste cazuri:
a=0, b=0
n acest caz soluia depinde valoarea lui c: c=0 => x iy poate fi orice numr ntreg c 0 => nu exist soluii
a=0, b0
Ecuaia devine: by=c. Deci y se poate calcula, innd ns cont cvorbim numai de numere ntregi.
a0, b= 0
Analog cu cazul anterior.
Dac unul dintre numerele a sau b are valoarea 1 nu se maipoate vorbi de penultima fracie de aproximare, deci i acestecazuri 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 lasfrit 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);
-
8/14/2019 Rezolvarea ecuatiilor diofantice
3/5
}
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...\n");}
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,yZ\n");else stop();
return 0;}else{ // by=cif (c%b) stop();
else { printf("xZ\n");printf("y=%ld\n",c/b);
}return 0;}
-
8/14/2019 Rezolvarea ecuatiilor diofantice
4/5
else{ //ax=cif (c%a) stop();
else {printf("x=%ld\n",c/a);
printf("yZ\n");
}return 0;
}
if (labs(m)==1)
{ // inseamna ca este de forma x+b*y=c, deci nuexista
// penultima fractie de aproximarex0=c*m;n1=-b*m;
y0=0;n2=1;return 1;}
elseif (labs(n)==1)
{ // inseamna ca este de forma a*xy=c, deci nuexista
// penultima fractie de aproximarex0=0;n1=1;y0=c*n;n2=-a*n;return 1;}
// m si n sunt diferite de 1, si diferite intre elem=labs(m);n=labs(n);while (m!=1){
if (m>n){ v[++nr]=m/n;m-=m/n*n;}
else if (m
-
8/14/2019 Rezolvarea ecuatiilor diofantice
5/5
if (b
