Page 32 - MATINF Nr. 13-14

32 V. P˘aun

3. Teorema permite ,,reconstruct , ia” unui num˘ar din resturile sale.

Demonstrat , ie:

Not˘am M i = M/m i . Deoarece (M i , m i ) = 1, exist˘ y i ∈ Z astfel ˆıncˆat:
a

M i y i ≡ 1 (mod m i ).

P
Definim x = a i M i y i . Pentru un indice fixat i, avem M j ≡ 0 (mod m i ) pentru j 6= i, deci:
a
x ≡ a i M i y i ≡ a i (mod m i ), ceea ce demonstreaz˘ existent , a solut , iei.
0
0
0
Dac˘a x s , i x sunt dou˘a solut , ii, atunci x ≡ x (mod m i ) pentru orice i, deci x − x este
a
multiplu de M, ceea ce arat˘ unicitatea modulo M.
Algoritmul general:
1. Se calculeaz˘a M= produsul tuturor modulelor.

2. Pentru fiecare i: M i = M/m i .

3. Se calculeaz˘a inversul modular y i al lui M i modulo m i (algoritmul lui Euclid extins).
P
4. Se calculeaz˘a x = a i M i y i .
5. Se reduce x modulo M.

Implementare ˆın C++
#include <iostream>
using namespace std;
/*Algoritmul extins al lui Euclid rezolva urmatoarea problema:
determina d=cmmdc(a,b) si doi intregi m si n astfel incat m*a+n*b=d.
*/
long long euclidExtins(long long a, long long b, long long &m, long long &n)
{
if ( b== 0) { m = 1; n = 0; return a; }
int d = euclidExtins(b,a % b, n, m);
n=n-(a/b)*m;
return d;
}

// Gaseste inversul modular al lui a modulo m
// Returneaza 0 daca nu exista (cand cmmdc(a,m) != 1)
long long invers(long long a, long long m)
{
long long x, y;
long long d = euclidExtins(a, m, x, y);
if (d!=1) return 0; // Nu exista invers
return (x%m+m)%m; // Asigura rezultat pozitiv
}

// implementeaza algoritmul TCR
// functia TCR returneaza 1 daca metoda este aplicabila
// (modulele sunt prime intre ele)
// sau 0 in caz contrar. In parametrii x si M avem solutia sistemuloi