h1. Teorema chineza a resturilor - generalizari si aplicatii

== include(page="template/implica-te/scrie-articole" user_id="MciprianM") ==
 
(Categoria _Matematica_, Autor _Adrian Vladu_)
 

h2. Scurta istorie

Se considera un numar de obiecte. Impartindu-le in grupuri de cate trei, raman doua negrupate. Impartindu-le in grupuri de cate cinci, raman trei. Impartindu-le in grupuri de cate sapte, raman doua. Cate obiecte sunt? Aceasta este problema enuntata de matematicianul chinez Sun-Tsu in secolul al IV-lea al erei noastre. El a demonstrat ca toate numerele naturale de forma <tex>23 + 105 * k</tex> reprezinta solutiile acestei probleme. Din pacate nu putem sti daca a dezvoltat o metoda generala pentru a rezolva astfel de sisteme de ecuatii modulare. Aceasta este tema tratata in articolul care urmeaza.

<p>Se considera un numar de obiecte. Impartindu-le in grupuri de cate trei, raman doua negrupate. Impartindu-le in grupuri de cate cinci, raman trei. Impartindu-le in grupuri de cate sapte, raman doua. Cate obiecte sunt? Aceasta este problema enuntata de matematicianul chinez Sun-Tsu in secolul al IV-lea al erei noastre. El a demonstrat ca toate numerele naturale de forma 23 + 105 {*} k reprezinta solutiile acestei probleme. Din pacate nu putem sti daca a dezvoltat o metoda generala pentru a rezolva astfel de sisteme de ecuatii modulare. Aceasta este tema tratata in articolul care urmeaza.</p>

h2. Definitie

Pentru inceput, sa consideram sirul <tex>n = n_{1}, n_{2}, ..., n_{k}</tex> ale carui elemente sunt, luate doua cate doua, prime intre ele. *Teorema chineza a restului* (t.c.r.) afirma ca exista o corespondenta biunivoca intre orice numar <tex>a\in\mathbb{Z}_{n}</tex> si multimea ordonata de resturi ale lui a modulo <tex>n_{i}, i\in\{1, 2, ..., k\}</tex>. Cu alte cuvinte, operatiile in <tex>\mathbb{Z}_{n}</tex> pot fi aplicate echivalent atat pe numere cat si pe multimile ordonate corespunzatoare resturilor modulo <tex>n_{i}</tex>. Pentru orice <tex>a, b \in \mathbb{Z}_{n}</tex>, notam <tex>a_{i} = a\ mod\ n</tex>, respectiv <tex>b_{i} = b\ mod\ n</tex>, generand corespondentele <tex>a \leftrightarrow \{a_{1}, a_{2}, ..., a_{k}\}</tex> respectiv <tex>b \leftrightarrow \{b_{1}, b_{2}, ..., b_{k}\}</tex>. Conform teoremei chineze a restului, pentru orice operator <tex>\circ \in \{+, -, * \}</tex>, <tex>a \circ b \leftrightarrow \{(a_{1} \circ b_{1})\ mod\ n_{1} , ( a_{2}\circ b_{2})\ mod\ n_{2}, ..., (a_{k} \circ b_{k})\ mod\ n_{k}\}</tex> ramane o corespondenta valida. 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. Pentru determinarea numarului <tex>x \in \mathbb{Z}_{n}</tex>, corespunzator multimii <tex>\{ a_{1}, a_{2}, ..., a_{k}\}</tex>, este suficienta rezolvarea sistemului de ecuatii modulare:
 
<tex>x \equiv a_{1}(mod\ n_{1})</tex>
<tex>x \equiv a_{2}(mod\ n_{2})</tex>
<tex>...</tex>
<tex>x \equiv a_{k}(mod\ n_{k})</tex>

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

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

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

*  se noteaza <tex>n = n_{1} * n_{2} * ... * n_{k}</tex> si <tex>M_{i}= n / n_{i}</tex> (deoarece oricare doua valori <tex>n_{i}</tex> si <tex>n_{j}</tex> sunt prime intre ele, avem intotdeauna <tex>cmmdc(M_i, n_i) = 1</tex>);
*  se calculeaza <tex>x_i</tex> , <tex>i \in \{1, 2, ..., k\}</tex> cu proprietatea <tex>M_i * x_i \equiv 1 (mod\ n_i)</tex>; cu alte cuvinte, avem <tex>x_i = M_i^{-1}\ mod\ n_i</tex>;
*  se determina <tex>x = (a_1 * M_1 * x_1 + a_2 * M_2 * x_2_ + ... + a_k * M_k * x_k)\ mod\ n</tex>.

         ...

Sa demonstram mai intai ca acesta valoare <tex>x</tex> satisface sistemul. Este necesar ca pentru orice <tex>i \in \{1, 2, ..., k\}</tex>, <tex>x \equiv a_i(mod\ n_i)</tex>. Mai exact, trebuie sa fie satisfacuta egalitatea <tex>((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>, <tex>\forall i \in \{1, 2, ..., k\}</tex>. Datorita faptului ca <tex>n_i | n</tex>, avem <tex>(a_1 * M_1 * x_1 + a_2 * M_2 * x_2 + ... + a_k * M_k * x_k)\ mod\ n_i = a_i</tex>. Stim ca <tex>M_i = n / n_i</tex>, <tex>\forall j \neq i</tex>, <tex>M_j\ mod\ n_i = 0</tex>, deci <tex>\forall j \neq i</tex>, <tex>(a_j * M_j * x_j)\ mod\ n_i = 0</tex>. Este suficient sa demonstram ca <tex>(a_i * M_i * x_i)\ mod\ n_i = a_i \Leftrightarrow (a_i * (M_i * x_i)\ mod\ n_i)\ mod\ n_i = a_i</tex>. Folosind <tex>M_i * x_i \equiv 1 (mod\ n_i)</tex> ajungem la egalitatea evidenta <tex>a_i = a_i</tex>(q.e.d.)

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

Mai ramane de verificat daca valoarea <tex>x</tex> este unica. Fie <tex>x'</tex> o alta solutie; avem <tex>x < n</tex> si <tex>x' < n</tex>. Daca <tex>x \equiv a_i (mod\ n_i)</tex> si <tex>x' \equiv a_i (mod\ n_i)</tex>, <tex>\forall i \in \{1, 2, ..., k\}</tex>, presupunand ca <tex>x' < x</tex>, avem <tex>x'-x \equiv 0 (mod\ n_i)</tex>, <tex>\forall i \in \{1, 2, ... k\}</tex>. Datorita faptului ca numerele <tex>n_i</tex> sunt relativ prime, rezulta ca <tex>x'-x = k * n</tex>, <tex>k \in \mathbb{Z}^*</tex>, deci <tex>x'-x \geq n</tex>, 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>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>

Pentru calcularea inversului modular al unui numar din <tex>\mathbb{Z}_n</tex>, 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 <tex>cmmdc(a, n) = 1</tex>. Aplicam algoritmul extins al lui Euclid si determinam <tex>x</tex> si <tex>y</tex> astfel incat <tex>a * x + n * y = 1</tex> si obtinem <tex>a^{-1} = x\ mod\ n</tex>; pentru a verifica observam ca egalitatea <tex>a^{-1} = x\ mod\ n</tex> este echivalenta cu <tex>a * (x\ mod\ n) \equiv 1 (mod\ n)</tex> care, la randul sau, este echivalenta cu <tex>a * x \equiv 1 (mod\ n)</tex>. Aceasta ultima afirmatie este evident adevarata deoarece avem <tex>a * x + n * y = 1</tex>. Pentru valori mici ale lui <tex>n</tex>, este recomandata preprocesarea "bruta" a inverselor tuturor numerelor <tex>a</tex> din <tex>\mathbb{Z}_n</tex> prime cu <tex>n</tex>, folosind doua structuri repetitive imbricate.
 
h2. Rezolvarea sistemelor de ecuatii modulare liniare generale

*  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>

O problema mai generala care ne-ar putea interesa este rezolvarea sistemelor de ecuatii modulare

<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>

<tex>x \equiv a_1(mod\ n_1)</tex>
<tex>x \equiv a_2(mod\ n_2)</tex>
<tex>...</tex>
<tex>x \equiv a_k(mod\ n_k)</tex>
 
unde <tex>n_1, n_2, ..., n_k</tex> nu sunt neaparat prime intre ele. Este suficienta generalizarea pentru un sistem de doua ecuatii. Din
<tex>x \equiv a_1(mod\ n_1)</tex>
<tex>x \equiv a_2(mod\ n_2)</tex>
se va obtine o a treia ecuatie <tex>x \equiv a_s (mod\ n_s)</tex> satisfacuta de orice valoare <tex>x</tex> cu proprietatea ca exista <tex>b_1, b_2 \in \mathbb{Z}</tex>, astfel incat <tex>x = n_1 * b_1 + a_1 = n_2 * b_2 + a_2</tex>. Pentru oricare astfel de valoare <tex>x</tex>, vom avea:
<tex>x \equiv a_1 (mod\ n_1)</tex>
si
<tex>x \equiv a_2 (mod\ n_2)</tex>.
Cu alte cuvinte, sistemul si noua ecuatie sunt echivalente.

<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>

Daca deteriminam valoarea <tex>x</tex> 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 <tex>n_1, n_2, ..., n_k</tex>. Din <tex>n_1 * b_1 + a_1 = n_2 * b_2 + a_2</tex> se obtine <tex>n_1 * b_1 - n_2 * b_2 = a_2 - a_1</tex>. Fie <tex>d = cmmdc(n_1, n_2)</tex>. Aplicand "algoritmul extins al lui Euclid":http://infoarena.ro/Algoritmul-lui-Euclid se determina valorile <tex>c_1</tex> si <tex>c_2</tex> astfel incat <tex>n_1 * c_1 + n_2 * c_2 = d</tex>. Amplificand cu <tex>(a_2 - a_1) / d</tex> se obtine: <tex>n_1 * c_1 * (a_2 - a_1) / d + n_2 * c_2 * (a_2 - a_1) / d = a_2 - a_1</tex>. Am putea fi tentati sa credem ca <tex>b_1 = c_1 * (a_2 - a_1) / d</tex> si <tex>b_2 = c_2 * (a_2 - a_1)</tex>, dar aceasta nu este intotdeauna cea mai buna solutie.

<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>

Fie <tex>h = cmmmc(n_1, n_2)</tex>, valoarea minima pentru care, daca <tex>x</tex> este solutie, atunci si <tex>x + h</tex> este solutie (cu alte cuvinte, <tex>h</tex> este perioada). Notand <tex>l = (a_2 - a_1) / d</tex>, observam ca <tex>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)</tex> satisface sistemul. Dorim sa gasim cea mai mica solutie, deci valoarea <tex>c_1 * l + k * h / n_1</tex> trebuie sa fie cat mai mica posibil. Fie <tex>m_1 = c_1 * l + k * h / n_1</tex>, iar <tex>n_1 * m_1 + b_1</tex> cea mai mica valoare care satisface sistemul. Stim ca <tex>n_1 * m_1 + b_1 < h</tex> si exista o singura solutie mai mica decat <tex>h</tex>. Avem <tex>h / n_1 > m_1 \geq 0</tex>, deci <tex>m_1 = (c_1 * l)\ mod\ (h / n_1)</tex>. Sistemul format din cele doua ecuatii este satisfacut pentru valorile <tex>x = cmmmc(n_1, n_2) * i + n_1 * m_1 + b_1</tex>, pentru <tex>i \geq 0</tex>. Sistemul este astfel echivalent cu <tex>x \equiv n_1 * m_1 + b_1 (mod\ cmmmc(n_1, n_2))</tex>.
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>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>

Limbajele de programare evalueaza gresit operatiile de forma $*a mod n*$ , atunci cand $a$ este un numar intreg negativ. Pentru a evita neplacerile ar trebui implementata o functie proprie pentru operatia modulo. Un exemplu este prezentat in continuare:

<p>Mai mult, verificand daca se pastreaza corespondenta in cazul aplicarii operatorilor, demonstrarea t.c.r. poate fi usor incheiata.</p>

==code(c) |
int mod(int a, int n) {
    a %= n;
    if (a < 0) a += n;
    return a;
}
==

<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.
 Pentru valori mici ale lui n, este recomandata preprocesarea "bruta" a inverselor tuturor
numerelor a din Z ~n~ prime cu n, folosind doua structuri repetitive imbricate.
</p>

h2. Teorema chineza intr-un sistem de sharing $k$-threshold

h2. Rezolvarea sistemelor de ecuatii modulare liniare generale

Se considera o informatie secreta codificata intr-un numar foarte mare <tex>N</tex>. Pentru a-l pastra in siguranta, acesta este impartit la <tex>n</tex> servere din tara. Daca <tex>p</tex> servere nu functioneaza, din diverse motive, <tex>N</tex> poate fi recuperat folosind <tex>n-p</tex> servere ramase, atata timp cat <tex>n-p \geq k</tex>, valoarea threshold.

<p>
O problema mai generala care ne-ar putea interesa este rezolvarea sistemelor de ecuatii modulare
x <tex>\equiv</tex> a ~1~ (mod n ~1~ )
x <tex>\equiv</tex> a ~2~ (mod n ~2~ )
...
x <tex>\equiv</tex> a ~k~ (mod n ~k~ )
unde n ~1~ , n ~2~ , ..., n ~k~ nu sunt neaparat prime intre ele. Este suficienta generalizarea pentru un sistem de doua ecuatii. Din
x <tex>\equiv</tex> a ~1~ (mod n ~1~ )
x <tex>\equiv</tex> a ~2~ (mod n ~2~ )
se va obtine o a treia ecuatie x <tex>\equiv</tex> a ~s~ (mod n ~s~ ) satisfacuta de orice valoare x cu proprietatea ca exista b ~1~ , b ~2~ <tex>\in</tex> Z, astfel incat x = n ~1~ {*} b ~1~ + a ~1~ = n ~2~ {*} b ~2~ + a ~2~ . Pentru oricare astfel de valoare x, vom avea:
x <tex>\equiv</tex> a ~1~ (mod n ~1~ )
si
x <tex>\equiv</tex> a ~2~ (mod n ~2~ ).
Cu alte cuvinte, sistemul si noua ecuatie sunt echivalente.
</p>

Alegand <tex>n</tex> numere prime <tex>p_1, p_2, ..., p_n</tex>, cuprinse intre <tex>N^{1/k}</tex> si <tex>N^{1/(k-1)}</tex>, <tex>N</tex> poate fi determinat folosind exact <tex>k</tex> servere, dar niciodata mai putine. Fiecare server <tex>i</tex> primeste catul si restul impartirii lui <tex>N</tex> la <tex>p_i</tex>. Pentru reconstituire se foloseste _t.c.r_, obtinandu-se astfel valoarea <tex>N</tex> cautata. Acest lucru este posibil deoarece alegand, fara a restrange generalitatea, primele <tex>k</tex> servere, se obtine o solutie modulo <tex>p_1 * p_2 * ... * p_k</tex>. Vom avea intotdeauna <tex>p_i > N^{1/k} * p_1 * p_2 * ... * p_n > N</tex>. Toate solutiile vor fi de forma <tex>x = (p_1 * p_2 * ...  * p_n) * i + x_0</tex>; dat fiind faptul prezentat anterior, ne intereseaza doar solutia cu <tex>i = 0</tex>. Presupunand ca se iau in considerare <tex>r < k</tex> servere, se obtin (din nou fara a restrange generalitatea) solutii de forma <tex>x = (p_1 * p_2 * ...  * p_r)  * i + x_0</tex>. Un adversar care cunoaste <tex>r</tex> secrete poate itera dupa <tex>i</tex>, incercand toate valorile posibile ale lui <tex>x</tex>. Desi initial am putea crede ca solutia va fi gasita usor, alegand o valoare <tex>p_i</tex> mult mai mica decat <tex>N^{1/(k-1)}</tex>, solutia generala va fi de forma <tex>x = M * i + x_0</tex>, unde <tex>M</tex> este mult mai mic decat <tex>N</tex>, aceasta lasand intrusului un numar imens de incercari, iar ghicirea valorii corecte devine practic imposibila.

<p>
Dacã 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 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~ .
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, dac x este solutie, atunci si x + h este solutie (cu alte
cuvinte, h este perioada).
Notând l = (a ~2~ - a ~1~ ) / d, observam ca n ~1~ {*} c ~1~ {*} l - n ~2~ {*} c ~
l + k · h - k · h = n1 · (c1 · l + k · h / n1) - n2 · (c2 · l + k · h
/ n2) satisface sistemul.
Dorim sã gãsim cea mai micã soluþie, deci valoarea c1
· l + k · h / n1 trebuie sã fie cât mai micã posibil. Fie m1 =
c1 · l + k · h / n1, iar n1 · m1 + b1 cea mai micã valoare care
satisface sistemul.
ªtim cã n1 · m1 + b1 < h ºi existã o singurã soluþie mai
micã decât h. Avem h / n1 > m1 ≥ 0, deci m1 = (c1 · l)
mod (h / n1).
Sistemul format din cele douã ecuaþii este satisfãcut
pentru valorile x = cmmmc(n1, n2) · i + n1 · m1 + b1, pentru
i ≥ 0.
Sistemul este astfel echivalent cu
x ≡ n1 · m1 + b1 (mod cmmmc(n1, n2)).
Pentru a rezolva un sistem de ecuaþii cu mai mult de
douã necunoscute este suficient sã aplicãm succesiv operaþiile
descrise mai sus, reducând perechile de ecuaþii la
una singurã echivalentã, pânã când rãmâne o singurã ecuaþie
modularã.
</p>
* acest articol trebuie imbunatatit

h2. Bibliografie
# Th. Cormen, Ch. Leiserson, R. Rivest, Introduction to Algorithms
# Donald E. Knuth, The Art of Computer Programming vol. 2 - Seminumerical Algorithms
# Sarad A.V aka Data, Applications to Chinese Remainder Theorem
# @***@ "Internet Problem Solving Contest 2005, Problem G - Gears in Action":http://ipsc.ksp.sk/contests/ipsc2005/real/problems/g.php

3685