Revizia anterioară Revizia următoare
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 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 ∈ 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 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 ∈ {+, -, * }, 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>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> x ࣕ a 1 (mod n 1 )
x ࣕ a 2 (mod n 2 )
...
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 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 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>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
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
