Diferente pentru teorema-chineza-a-resturilor intre reviziile #63 si #64

Nu exista diferente intre titluri.

Diferente intre continut:

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})\newline
x \equiv a_{2}(mod\ n_{2})\newline
...\newline
x \equiv a_{k}(mod\ n_{k})</tex>
<tex>x \equiv a_{1}(mod\ n_{1})</tex>
<tex>x \equiv a_{2}(mod\ n_{2})</tex>
...
<tex>x \equiv a_{k}(mod\ n_{k})</tex>
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:
*  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)$;

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.