<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>\lefteightarrow</tex> {b ~1~ , b ~2~ , ..., b ~k~ }. Conform teoremei chineze a restului, pentru orice operator op <tex>\in</tex> {+, -, * }, a op b <tex>\leftrightarrow</tex> {(a ~1~ op b ~1~) mod n ~1~ , (a ~2~ op b ~2~ )mod n ~2~ , ..., (a ~k~ op 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 &#2261; a ~1~ (mod n ~1~ )

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

        x ࣕ a ~2~ (mod n ~2~ )

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

         ...

        x ࣕ 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 &#8712; 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 ∈ {1, 2, ..., k} cu proprietatea M ~i~ {*} x ~i~ ࣕ 1 (mod n ~i~ ); cu alte cuvinte, avem x ~i~ = M ~i~ -1 mod n ~i~ ;

*  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 � {1, 2, ..., k}, x � 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~ , � i � {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~, pentru orice j � i, M ~j~ mod n ~i~ = 0, deci oricare ar fi j � 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~ � (a ~i~ {*} (M ~i~ {*} x ~i~ ) mod n ~i~ ) mod n ~i~ = a ~i~ . Folosind M ~i~ {*} x ~i~ � 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. Dacã  x &#2261; a ~i~ (mod n ~i~ ) si x ^'^ x &#2261; a ~i~ (mod n ~i~ ), oricare ar fi i &#8712; {1, 2, ..., k}, presupunand ca x ^'^ < x, avem x ^'6^ - x &#2261; 0 (mod n ~i~ ), oricare ar fi i &#8712; {1, 2, ... k}.</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 &#8712; Z ^*^ , deci x ^'^ - x � n, ceea ce contrazice ipoteza initiala. Asadar, solutia este unica, asa cum poate fi dedus si din t.c.r.</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>