Teorema chineza a resturilor - generalizari si aplicatii

Scurta istorie

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

Definitie

<p>Pentru inceput, sa consideram sirul n = n ₁ , n ₂ , ..., 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 Z _n si multimea ordonata de resturi ale lui a modulo n _i , i {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 Z _n, notam a _i = a mod n, respectiv b _i = b mod n, generand corespondentele a {a ₁ , a ₂ , ..., a _k } respectiv b [Unparseable or potentially dangerous LaTeX formula! Error 5 : 1020x1320] {b ₁ , b ₂ , ..., b _k }. Conform teoremei chineze a restului, pentru orice operator op {+, -, * }, a op b {(a ₁ op b ₁) mod n ₁ , (a ₂ op b ₂ )mod n ₂ , ..., (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 ₁ , a ₂ , ..., a _k }, este suficienta rezolvarea sistemului de ecuatii modulare:</p>

<p>  x ࣕ a ₁ (mod n ₁ )

  x ࣕ a ₂ (mod n ₂ )

  ...

  x ࣕ a _k (mod n _k )
</p>

<p>Deoarece avem de a face cu o corespondenta biunivoca, conform teoremei, exista un singur x ∈ 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 ₁ • n ₂ • ... • 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 determina x = (a ₁ • M ₁ • x ₁ + a ₂ • M ₂ • x ₂ + ... + 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>Mai exact, trebuie sa fie satisfacuta egalitatea ((a ₁ • M ₁ • x ₁ + a ₂ • M ₂ • x ₂ + ... + 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 ₁ • M ₁ • x ₁ + a ₂ • M ₂ • x ₂ + ... + 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 ࣕ a _i (mod n _i ) si x ^' x ࣕ a _i (mod n _i ), oricare ar fi i ∈ {1, 2, ..., k}, presupunand ca x ^' < x, avem x ^'6 - x ࣕ 0 (mod n _i ), oricare ar fi i ∈ {1, 2, ... k}.</p>

<p>Datorita faptului ca numerele n _i sunt relativ prime, rezulta ca x ^' - x = k • n, k ∈ 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>

• acest articol trebuie imbunatatit