For distinct primes p and q the Chinese Remainder problem is

For distinct primes p and q the Chinese Remainder problem is: Find x, 0

Solution

x_p= x mod p

and x_q= x mod q

x = np+x_p and also x = mq+x_q for m and n integers

np -mq + x_p-x_q=0

x_p-x_q = mq-np

q_inv= q^-1 mod p

Or q_inv= q^-1+pn\' for an integer n\'

(x_p-x_q ) q_inv = (mq-np)( q^-1+pn\') = m-npq^-1+mqpn\'-npq^-1-nn\'

(x_p-x_q ) q_inv mod p =m-nn\'

Hence x_q +hq = x_q +m-nn\'

= x

Hence proved