Diferente pentru teorema-chineza-a-resturilor intre reviziile #66 si #67

Nu exista diferente intre titluri.

Diferente intre continut:

Deoarece avem de a face cu o corespondenta biunivoca, conform teoremei, exista un singur <tex>x \in \mathbb{Z}_{n}</tex> care satisface sistemul de mai sus. Procedeul prin care se determina aceasta valoare nu este deosebit de complicat:
*  se noteaza <tex>n = n_{1} * n_{2} * ... * n_{k}</tex> si <tex>M_{i}= n / n_{i}</tex> (deoarece oricare doua valori <tex>n_{i}</tex> si <tex>n_{j}</tex> sunt prime intre ele, avem intotdeauna <tex>cmmdc(M_i, n_i) = 1</tex>);
*  se calculeaza $x{~i~}$ , $i$ <tex>\in</tex> ${1, 2, ..., k}$ cu proprietatea $M{~i~}{*} x{~i~}$ <tex>\equiv</tex> $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$.
*  se calculeaza <tex>x_i</tex> , <tex>i \in \{1, 2, ..., k\}</tex> cu proprietatea <tex>M_i * x_i \equiv 1 (mod\ n_i)</tex>; cu alte cuvinte, avem <tex>x_i = M_i-1 mod\ n_i</tex>;
*  se determina <tex>x = (a_1 * M_1 * x_1 + a_2 * M_2 * x_2_ + ... + a_k * M_k * x_k) mod\ n</tex>.
Sa demonstram mai intai ca acesta valoare $x$ satisface sistemul. Este necesar ca pentru orice $i$ <tex>\in</tex>${1, 2, ..., k}$, $x$ <tex>\equiv</tex> $a{~i~}(mod n{~i~})$. 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~}$ , <tex>\forall</tex> $i$ <tex>\in</tex> ${1, 2, ..., k}$. 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~}$ , <tex>\forall</tex> $j$ <tex>\neq</tex> $i$ , $M{~j~} mod n{~i~}= 0$, deci <tex>\forall</tex> $j$ <tex>\neq</tex>$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~}$ <tex>\Leftrightarrow</tex>$(a{~i~}{*} (M{~i~}{*} x{~i~}) mod n{~i~}) mod n{~i~}= a{~i~}$ . Folosind $M{~i~}{*} x{~i~}$ <tex>\equiv</tex> $1 (mod n{~i~})$ ajungem la egalitatea evidenta $a{~i~}= a{~i~}$ (q.e.d.)

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.