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.
- acest articol trebuie imbunatatit
