# Chinese Remainder Theorem Consequence

I am reviewing the proof of the Chinese Remainder Theorem and I am confused at one of the concluding sentences in my textbook. I understand why there is a solution for relatively prime $m,n$ such that for arbitrary integers $s,t$ that $x \equiv s$ (mod m) and $x \equiv t$ (mod n) but the concluding sentence says that now the solution is $x$ mod(mn) . I do not understand this last statement.

• In the proof we took mp+nq=1 by Bezout, and x=mpt+nqs then x-s=mpt+(nq-1)s=mp(t-s) thus x is equivalent to s mod m, and similarly for t. – IntegrateThis Feb 24 '16 at 1:26

## 1 Answer

If $x \equiv s \pmod m$ this implies that $x=mk+s$

Since $x \equiv t \mod n$ $mk \equiv t-s \pmod n$.

Let the inverse of $m$ $\pmod n$ be $l$.

Then notice that $k \equiv l(t-s) \pmod n$.

Thus $k=np+l(t-s)$.

Thus the solutions are of the form $mnp+kl(t-s)+s \equiv x \pmod {mn}$.

Note that $k,l,s$ are all fixed integers.

Thus, all solutions have the same residue divided by $mn$.

So for all solutions $q$, $q \equiv x \pmod {mn}$.

• can you elaborate how you got that mnp + kl(t-s) + s $\equiv$ x mod (mn) – IntegrateThis Feb 24 '16 at 1:39
• @JamesDickens Because we set $x=mk+s$ and $k=np+l(t-s)$. – S.C.B. Feb 24 '16 at 1:42