Chinese Remainder Theorem --another proof x  k i (mod m i ) for 1≤i≤n, mi and mj are relatively prime (i j ) Note that M m m 2   1   m n  ,[ ] x m )n ,[ k ] n m n ) m n M M m 1   ([ ] x    , )    ([ ] f x m 1 If there exists x0, such that ([ ([ ) ] ] f x k  0 1 m M 1 (1, ,0, ,0)[ k    1   (0, ,1,  ,     (0,    ,0, ,0)[ ,0)[ ] k 1 m 1   ,1)[ ,0, k k ,  ] m 1 ] i m i ] n m n Let’s construct such xi which satisfies [ ] x i m i [ ] x i m 1 0,(    ) j i j f ] ([ x i M m x i m x i | | j i )    (0, ,1, ,0)   m m m 1 i 1  i  1  m x i | n Let’s consider Mx  m i i j gcd( ) 1 , m m   i j gcd( ) 1 , m m    i j i  ] i May be [ i mx 1 [ ] x x  m i i i  isn’t equal to one. We find its multipilative inverse with mod mi, 1  1 ix  . 

  x 0    n  i 1  1 x  i  x k  i i    M On the other hand, (1, ……, 1) is the generator of So x0(1, ……, 1) = (k1, ……, kn)?    . m n   m 1