h2. Definitie
<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 &#8712; Z ~n~ si multimea ordonata de resturi ale lui a modulo n ~i~ , i &#8712; {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 &#8712; Z ~n~, notam a ~i~ = a mod n, respectiv b ~i~ = b mod n, generand corespondentele a corespondent cu {a ~1~ , a ~2~ , ..., a ~k~ } respectiv b corespondent cu {b ~1~ , b ~2~ , ..., b ~k~ }. Conform teoremei chineze a restului, pentru orice operator op &#8712; {+, -, * }, a op b corespondent cu {(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>*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>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  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~ )

*  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 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 � {1, 2, ..., k}, x � 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~ , � i � {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~, 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

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. 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>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 &#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>Mai mult, verificand daca se pastreaza corespondenta in cazul aplicarii operatorilor, demonstrarea t.c.r. poate fi usor incheiata.</p>