Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-01-10 14:09:56.
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 în 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.
* acest articol trebuie imbunatatit