Page 33 - MATINF Nr. 13-14

a
Teorema chinezeasc˘ a resturilor 33

int TCR(long long a[],long long m[],int n, long long &x, long long &M )
{
M = 1;
for (int i = 0; i < n; i++)
M *= m[i];
x = 0;
for (int i = 0; i < n; i++) {
long long Mi = M / m[i];
long long yi = invers(Mi, m[i]);
if(yi==0) return 0;
x += a[i] * Mi * yi;
}
x = (x % M + M) % M;
return 1;
}

int main() {
long long a[100], m[100];
int n;
cout<<''Numar congruente de forma x=a(mod m) :'';
cin >> n;
cout<<''Tastati ''<<n<<'' congruente (a,m):''<<endl;
for (int i = 0; i < n; i++)
cin >> a[i] >> m[i];
long long x, M;
int r=TCR(a,m,n,x,M);
if(r)cout <<''solutie: ''<< x<<''(mod ''<<M<<'')'';
else cout<<''Metoda nu se poate aplica: modulele nu sunt prime intre ele'';
return 0;
}

Cˆand modulele m 1 , m 2 , . . . , m k nu sunt prime ˆıntre ele (adic˘a cel put , in dou˘a au un divizor
comun mai mare ca 1), algoritmul clasic prezentat anterior nu poate fi aplicat direct deoarece
a
inversele modulare s-ar putea s˘ nu existe.
ˆ
In acest caz, sistemul de ecuat , ii poate s˘a nu aib˘a nicio solut , ie sau s˘a aib˘a o solut , ie unic˘a
modulo [m 1 , m 2 , . . . , m k ] (cel mai mic multiplu comun).

a
lat˘ pas , ii de rezolvare:
a
1. Condit , ia de existent , ˘ (Criteriul de consistent , ˘a)
Pentru ca un sistem de dou˘a ecuat , ii:

x ≡ a 1 (mod m 1 )

x ≡ a 2 (mod m 2 )
s˘a aib˘a solut , ie, trebuie neap˘arat ca a 1 − a 2 s˘a fie divizibil cu cmmdc(m 1 , m 2 ). Dac˘a aceast˘a
condit , ie nu este ˆındeplinit˘a, sistemul este inconsistent (nu exist˘a niciun x care s˘a satisfac˘a
ambele condit , ii).

2. Metoda rezolv˘arii succesive (Metoda substitut , iei)
a
a
Dac˘ solut , ia exist˘a, nu mai folosim formula direct˘ cu M i , ci reducem sistemul pas cu pas.