*  se calculeaza $x{~i~}$ , $i$ <tex>\in</tex> ${1, 2, ..., k}$ cu proprietatea $M{~i~}{*} x{~i~}$ <tex>\equiv</tex> $1 (mod n{~i~})$; cu alte cuvinte, avem $x{~i~}= M{~i~}-1 mod n{~i~}$ ;
*  se determina $x = (a{~1~} {*} M{~1~}{*} x{~1~}+ a{~2~}{*} M{~2~}{*} x{~2~}+ ... + a{~k~}{*} M{~k~}{*} x{~k~}) mod n$.

<p>Sa demonstram mai intai ca acesta valoare $x$ satisface sistemul. Este necesar ca pentru orice $i$ <tex>\in</tex>${1, 2, ..., k}$, $x$ <tex>\equiv</tex> $a{~i~}(mod n{~i~})$.</p>
 
<p>Mai exact, trebuie sa fie satisfacuta egalitatea $((a{~1~}{*} M{~1~}{*} x{~1~}+ a{~2~}{*} M{~2~}{*} x{~2~}+ ... + a{~k~}{*} M{~k~}{*} x{~k~}) mod n) mod n{~i~}= a{~i~}$ , <tex>\forall</tex> $i$ <tex>\in</tex> ${1, 2, ..., k}$.</p>
 
<p>Datorita faptului ca $n{~i~}| n$, avem $(a{~1~}{*} M{~1~}{*} x{~1~}+ a{~2~}{*} M{~2~}{*} x{~2~}+ ... + a{~k~}{*} M{~k~}{*} x{~k~}) mod n{~i~}= a{~i~}$ . Stim ca $M{~i~}= n / n{~i~}$ , <tex>\forall</tex> $j$ <tex>\neq</tex> $i$ , $M{~j~} mod n{~i~}= 0$, deci <tex>\forall</tex> $j$ <tex>\neq</tex>$i$, $(a{~j~} {*} M{~j~}{*} x{~j~}) mod n{~i~}= 0$. Este suficient sa demonstram ca $(a{~i~}{*} M{~i~}{*} x{~i~}) mod n{~i~}= a{~i~}$ <tex>\Leftrightarrow</tex>$(a{~i~}{*} (M{~i~}{*} x{~i~}) mod n{~i~}) mod n{~i~}= a{~i~}$ . Folosind $M{~i~}{*} x{~i~}$ <tex>\equiv</tex> $1 (mod n{~i~})$ ajungem la egalitatea evidenta

<p>Sa demonstram mai intai ca acesta valoare $x$ satisface sistemul. Este necesar ca pentru orice $i$ <tex>\in</tex>${1, 2, ..., k}$, $x$ <tex>\equiv</tex> $a{~i~}(mod n{~i~})$. Mai exact, trebuie sa fie satisfacuta egalitatea $((a{~1~}{*} M{~1~}{*} x{~1~}+ a{~2~}{*} M{~2~}{*} x{~2~}+ ... + a{~k~}{*} M{~k~}{*} x{~k~}) mod n) mod n{~i~}= a{~i~}$ , <tex>\forall</tex> $i$ <tex>\in</tex> ${1, 2, ..., k}$. Datorita faptului ca $n{~i~}| n$, avem $(a{~1~}{*} M{~1~}{*} x{~1~}+ a{~2~}{*} M{~2~}{*} x{~2~}+ ... + a{~k~}{*} M{~k~}{*} x{~k~}) mod n{~i~}= a{~i~}$ . Stim ca $M{~i~}= n / n{~i~}$ , <tex>\forall</tex> $j$ <tex>\neq</tex> $i$ , $M{~j~} mod n{~i~}= 0$, deci <tex>\forall</tex> $j$ <tex>\neq</tex>$i$, $(a{~j~} {*} M{~j~}{*} x{~j~}) mod n{~i~}= 0$. Este suficient sa demonstram ca $(a{~i~}{*} M{~i~}{*} x{~i~}) mod n{~i~}= a{~i~}$ <tex>\Leftrightarrow</tex>$(a{~i~}{*} (M{~i~}{*} x{~i~}) mod n{~i~}) mod n{~i~}= a{~i~}$ . Folosind $M{~i~}{*} x{~i~}$ <tex>\equiv</tex> $1 (mod n{~i~})$ ajungem la egalitatea evidenta

$a{~i~}= a{~i~}$ (q.e.d.)</p>

<p>Mai ramane de verificat daca valoarea $x$ este unica. Fie $x^'^$ o alta solutie; avem $x < n$ si $x^'^ < n$. Daca  {$x$} <tex>\equiv</tex> $a{~i~}(mod n{~i~})$ si $x^'^$ <tex>\equiv</tex> $a{~i~}(mod n{~i~})$, <tex>\forall</tex> $i$ <tex>\in</tex> ${1, 2, ..., k}$, presupunand ca $x^'^ < x$, avem $x^'^ - x$ <tex>\equiv</tex> $0 (mod n{~i~})$, <tex>\forall</tex> $i$ <tex>\in</tex> ${1, 2, ... k}$.</p>
 
<p>Datorita faptului ca numerele $n{~i~}$ sunt relativ prime, rezulta ca $x^'^ - x = k {*} n$, $k$ <tex>\in</tex> $Z^*^$ , deci $x^'^ - x$ <tex>\geq</tex>$n$, ceea ce contrazice ipoteza initiala. Asadar, solutia este unica, asa cum poate fi dedus si din t.c.r.</p>
 
<p>Mai mult, verificand daca se pastreaza corespondenta in cazul aplicarii operatorilor, demonstrarea t.c.r. poate fi usor incheiata.</p>

<p>Mai ramane de verificat daca valoarea $x$ este unica. Fie $x^'^$ o alta solutie; avem $x < n$ si $x^'^ < n$. Daca  {$x$} <tex>\equiv</tex> $a{~i~}(mod n{~i~})$ si $x^'^$ <tex>\equiv</tex> $a{~i~}(mod n{~i~})$, <tex>\forall</tex> $i$ <tex>\in</tex> ${1, 2, ..., k}$, presupunand ca $x^'^ < x$, avem $x^'^ - x$ <tex>\equiv</tex> $0 (mod n{~i~})$, <tex>\forall</tex> $i$ <tex>\in</tex> ${1, 2, ... k}$. Datorita faptului ca numerele $n{~i~}$ sunt relativ prime, rezulta ca $x^'^ - x = k {*} n$, $k$ <tex>\in</tex> $Z^*^$ , deci $x^'^ - x$ <tex>\geq</tex>$n$, ceea ce contrazice ipoteza initiala. Asadar, solutia este unica, asa cum poate fi dedus si din t.c.r. Mai mult, verificand daca se pastreaza corespondenta in cazul aplicarii operatorilor, demonstrarea t.c.r. poate fi usor incheiata.</p>

<p>
 Pentru calcularea inversului modular al unui numar din $Z{~n~}$ , de obicei se foloseste "algoritmul extins al lui Euclid":http://infoarena.ro/Algoritmul-lui-Euclid. Evident, pentru ca acest invers sa existe, trebuie sa avem $cmmdc(a, n) = 1$. Aplicam algoritmul extins al lui Euclid si determinam $x$ si $y$ astfel incat $a {*} x + n {*} y = 1$ si obtinem $a^-1^ = x mod n$; pentru a verifica observam ca egalitatea $a^-1^ = x mod n$ este echivalenta cu $a {*} (x mod n)$ <tex>\equiv</tex> $1 (mod n)$ care, la randul sau, este echivalenta cu $a {*} x$ <tex>\equiv</tex> $1 (mod n)$. Aceasta ultima afirmatie este evident adevarata deoarece avem $a {*} x + n {*} y = 1$.

<p>
Daca deteriminam valoarea $x$ minima care satisface sistemul de ecuatii modulare, toate celelalte solutii vor fi obtinute adunand la acesta un multiplu al celui mai mic multiplu comun al numerelor $n{~1~}$ , $n{~2~}$ , ..., $n{~k~}$ .

Din $n{~1~}{*} b{~1~}+ a{~1~}= n{~2~}{*} b{~2~}+ a{~2~}$ se obtine $n{~1~}{*} b{~1~}- n{~2~}{*} b{~2~}$
$= a{~2~}- a{~1~}$ .

Din $n{~1~}{*} b{~1~}+ a{~1~}= n{~2~}{*} b{~2~}+ a{~2~}$ se obtine $n{~1~}{*} b{~1~}- n{~2~}{*} b{~2~}= a{~2~}- a{~1~}$ .

Fie $d = cmmdc(n{~1~}, n{~2~})$. Aplicand "algoritmul extins al lui Euclid":http://infoarena.ro/Algoritmul-lui-Euclid se determina valorile $c{~1~}$ si $c{~2~}$ astfel incat $n{~1~}{*} c{~1~}+ n{~2~}{*} c{~2~}= d$.

Amplificand cu $(a{~2~}- a{~1~}) / d$ se obtine:
 $n{~1~}{*} c{~1~}{*} (a{~2~}- a{~1~}) / d + n{~2~}{*} c{~2~}{*} (a{~2~}- a{~1~}) / d = a{~2~}- a{~1~}$ .

Amplificand cu $(a{~2~}- a{~1~}) / d$ se obtine: $n{~1~}{*} c{~1~}{*} (a{~2~}- a{~1~}) / d + n{~2~}{*} c{~2~}{*} (a{~2~}- a{~1~}) / d = a{~2~}- a{~1~}$ .

Am putea fi tentati sa credem ca $b{~1~}= c{~1~}{*} (a{~2~}- a{~1~}) / d$ si $b{~2~}= c{~2~}{*} (a{~2~}- a{~1~})$, dar aceasta nu este intotdeauna cea mai buna solutie. Fie $h = cmmmc(n{~1~}, n{~2~})$, valoarea minima pentru care, daca $x$ este solutie, atunci si $x + h$ este solutie (cu alte cuvinte, $h$ este perioada).

Notand $l = (a{~2~}- a{~1~}) / d$, observam ca $n{~1~}{*} c{~1~}{*} l - n{~2~}{*} c{~2~}{*} l + k {*} h - k {*} h = n{~1~}{*} (c{~1~}{*} l + k {*} h / n{~1~}) - n{~2~}{*} (c{~2~}{*} l + k {*} h/ n{~2~})$ satisface sistemul.
Dorim sa gasim cea mai mica solutie, deci valoarea $c{~1~}{*} l + k {*} h / n{~1~}$ trebuie sa fie cat mai mica posibil. Fie $m{~1~}= c{~1~}{*} l + k {*} h / n{~1~}$ , iar $n{~1~}{*} m{~1~}+ b{~1~}$ cea mai mica valoare care satisface sistemul.
Stim ca $n{~1~}{*} m{~1~}+ b{~1~}< h$ si exista o singura solutie mai mica decat $h$. Avem $h / n{~1~}> m{~1~}$ <tex>\geq</tex> $0$, deci $m{~1~}= (c{~1~}{*} l) mod (h / n{~1~})$.
Sistemul format din cele doua ecuatii este satisfacut pentru valorile $x = cmmmc(n{~1~}, n{~2~}) {*} i + n{~1~}{*} m{~1~}+ b{~1~}$ , pentru $i$ <tex>\geq</tex> $0$.

Notand $l = (a{~2~}- a{~1~}) / d$, observam ca $n{~1~}{*} c{~1~}{*} l - n{~2~}{*} c{~2~}{*} l + k {*} h - k {*} h = n{~1~}{*} (c{~1~}{*} l + k {*} h / n{~1~}) - n{~2~}{*} (c{~2~}{*} l + k {*} h/ n{~2~})$ satisface sistemul. Dorim sa gasim cea mai mica solutie, deci valoarea $c{~1~}{*} l + k {*} h / n{~1~}$ trebuie sa fie cat mai mica posibil. Fie $m{~1~}= c{~1~}{*} l + k {*} h / n{~1~}$ , iar $n{~1~}{*} m{~1~}+ b{~1~}$ cea mai mica valoare care satisface sistemul. Stim ca $n{~1~}{*} m{~1~}+ b{~1~}< h$ si exista o singura solutie mai mica decat $h$. Avem $h / n{~1~}> m{~1~}$ <tex>\geq</tex> $0$, deci $m{~1~}= (c{~1~}{*} l) mod (h / n{~1~})$. Sistemul format din cele doua ecuatii este satisfacut pentru valorile $x = cmmmc(n{~1~}, n{~2~}) {*} i + n{~1~}{*} m{~1~}+ b{~1~}$ , pentru $i$ <tex>\geq</tex> $0$.

Sistemul este astfel echivalent cu $x$ <tex>\equiv</tex> $n{~1~}{*} m{~1~}+ b{~1~}(mod cmmmc(n{~1~}, n{~2~}))$.
Pentru a rezolva un sistem de ecuatii cu mai mult de doua necunoscute este suficient sa aplicam succesiv operatiile descrise mai sus, reducand perechile de ecuatii la una singura echivalenta, pana cand ramane o singura ecuatie modulara.
</p>