<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>    $x$ <tex>\equiv</tex> $a{~1~} (mod n{~1~})$

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

        $x$ <tex>\equiv</tex> $a{~2~} (mod n{~2~})$

         ...

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

        $x$ <tex>\equiv</tex> $a{~k~} (mod n{~k~})$

</p>

<p>Deoarece avem de a face cu o corespondenta biunivoca, conform teoremei, exista un singur $x$ <tex>\in</tex> $Z ~n~$ care satisface sistemul de mai sus. Procedeul prin care se determina aceasta valoare nu este deosebit de complicat:

<p>Deoarece avem de a face cu o corespondenta biunivoca, conform teoremei, exista un singur $x$ <tex>\in</tex> $Z{~n~}$ care satisface sistemul de mai sus. Procedeul prin care se determina aceasta valoare nu este deosebit de complicat:

</p>

*  se noteaza $n = n ~1~ {*} n ~2~  {*} ... {*} n ~k~$ si $M ~i~ = n / n ~i~$ (deoarece oricare doua valori $n ~i~$ si $n ~j~$ sunt prime intre ele, avem intotdeauna $cmmdc(M ~i~, n ~i~ ) = 1)$;
*  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$.

*  se noteaza $n = n{~1~} {*} n{~2~} {*} ... {*} n{~k~}$ si $M{~i~} = n / n{~i~}$ (deoarece oricare doua valori $n{~i~}$ si $n{~j~}$ sunt prime intre ele, avem intotdeauna $cmmdc(M{~i~}, n{~i~} ) = 1)$;
*  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>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>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
$a ~i~ = a ~i~$ (q.e.d.)</p>