Teorema cinese dei resti

[matilde08]

Qualcuno può dirmi come si risolve un sistema attraverso il teorema cinese dei resti?

Ad esempio:

$\{x-=1 (2), x-=2 (5), x-=3 (9)$


Grazie!

[Lord K]

Il teorema cita che la soluzione è del tipo $alpha_0$ comunque modulo $90=2*5*9$. Per trovarla basta seguire la dimostrazione del teorema:

Sia ${x \equiv a_i(n_i)}_(i=1...k)$ il sistema di congruenze, dove $MCD(n_i,n_j)=1$ con $i!=j$.

Sia $N=prod_(i=1)^k n_i$, allora $MCD(N/n_i,n_i)=1$

Da questo molto semplicemente possiamo considerare che esistono due interi $r_i,s_i in ZZ$ tali che: $r_i*n_i+s*N/n_i =1$.
Consideriamo $lambda_i = s*N/n_i$ allora di certo ho che:

${lambda_i=delta_(i,j) (n_j)}$ dove $delta_(i,j)={(1, i=j),(0, i!=j):}

Allora la soluzione al sistema di congruenze è del tipo:

$x \equiv sum_(i=1)^k a_i*e_i(N)$

Nell'esempio posto hai che:

${(x \equiv1 (2)),(x \equiv2 (5)),(x \equiv 3(9)):}$

$N=2*5*9$

E abbiamo che valgono:

$45*1-22*2=1$
$18*2-7*5=1$
$10*1-9*1=1$

Allora la soluzione è:

$x \equiv sum_(i=1)^k a_i*e_i(N) \equiv 45*1+36*2+10*3(90) \equiv 57(90)$