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.

  • $\begingroup$ 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. $\endgroup$ – IntegrateThis Feb 24 '16 at 1:26

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}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.