<p>Pentru inceput, sa consideram sirul $n = n{~1~}, n{~2~}, ..., n{~k~}$ ale carui elemente sunt, luate doua cate doua, prime intre ele.</p>
<p>*Teorema chineza a restului* (t.c.r.) afirma ca exista o corespondenta biunivoca intre orice numar $a$ <tex>\in</tex> $Z{~n~}$ si multimea ordonata de resturi ale lui a modulo $n{~i~}$, $i$ <tex>\in</tex> ${1, 2, ..., k}$. Cu alte cuvinte, operatiile in $Z{~n~}$ pot fi aplicate echivalent atat pe numere cat si pe multimile ordonate corespunzatoare resturilor modulo $n{~i~}$.<p>

<p>Pentru orice $a$, $b$ <tex>\in</tex> $Z{~n~}$, notam $a{~i~} = a mod n$, respectiv $b{~i~} = b mod n$, generand corespondentele $a$ <tex>\leftrightarrow</tex> ${a{~1~} ,  a{~2~} , ..., a{~k~}}$ respectiv $b$ <tex>\leftrightarrow</tex> ${ b{~1~}, b{~2~}, ..., b{~k~}}$. Conform teoremei chineze a restului, pentru orice operator <tex>\circ</tex> <tex>\in</tex> {+, -, * }, $a$ <tex>\circ</tex> $b$ <tex>\leftrightarrow</tex> ${(a{~1~}$ <tex>\circ</tex> $b{~1~}) mod n{~1~}$ , $(a ~2~$<tex>\circ</tex> $b ~2~ )mod n ~2~$ , ..., $(a ~k~$$ <tex>\circ</tex> $b ~k~ ) mod n ~k~ }$ ramane o corespondenta valida.</p>

<p>Pentru orice $a$, $b$ <tex>\in</tex> $Z{~n~}$, notam $a{~i~} = a mod n$, respectiv $b{~i~} = b mod n$, generand corespondentele $a$ <tex>\leftrightarrow</tex> ${a{~1~} ,  a{~2~} , ..., a{~k~}}$ respectiv $b$ <tex>\leftrightarrow</tex> ${ b{~1~}, b{~2~}, ..., b{~k~}}$. Conform teoremei chineze a restului, pentru orice operator <tex>\circ</tex> <tex>\in</tex> {+, -, * }, $a$ <tex>\circ</tex> $b$ <tex>\leftrightarrow</tex> ${(a{~1~}$ <tex>\circ</tex> $b{~1~}) mod n{~1~}$ , $(a ~2~$<tex>\circ</tex> $b ~2~ )mod n ~2~$ , ..., $(a ~k~$ <tex>\circ</tex> $b ~k~ ) mod n ~k~ }$ ramane o corespondenta valida.</p>

<p>Problema care se iveste imediat este conversia dintr-o forma in alta. Transformarea unui numar in multimea corespunzatoare este imediata. Partea mai dificila este operatia inversa, iar aceasta este problema care va fi tratata in continuare.</p>

<p>Pentru determinarea numarului $x$<tex>\in</tex>$Z ~n~ $, corespunzator multimii ${a ~1~ , a ~2~ , ..., a ~k~ }$, este suficienta rezolvarea sistemului de ecuatii modulare:</p>

<p>Pentru determinarea numarului $x$ <tex>\in</tex> $Z ~n~$, corespunzator multimii ${a ~1~ , a ~2~ , ..., a ~k~ }$, este suficienta rezolvarea sistemului de ecuatii modulare:</p>

 <p>    $x$ <tex>\equiv</tex> $a ~1~ (mod n ~1~ )$

<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>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>
<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~$ .

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~$ .

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~$ .