I read up on the Wikipedia article on the Chinese Remainder Theorem, and I understand the concepts. However, I am wondering how it can apply to the following (which is slightly different from their example):
$$a = (k\bmod{m})$$
$$b = (k\bmod{n})$$
where $m$ and $n$ are relatively prime. Also, $a$ and $b$ are constants. How can I prove that $k$ is unique given $0\le k < mn$. Does this fall under the theorem?
Many thanks!
Best Answer
Translating the mod operations into more convenient congruences we have
$$\begin{align}k\bmod m &=\, a\\ k\bmod n \ &=\, b\end{align}\ \Rightarrow\ \begin{array}{}k\equiv a\pmod{\!m}\\ k\equiv b\pmod{\!n} \end{array}\qquad$$
By $m,n$ coprime, CRT $\Rightarrow$ the RHS congruence system has a $\rm\color{#c00}{unique}$ solution $\!\pmod{\!mn}.\,$ So there is exactly $\rm\color{#c00}{one}$ solution $k$ in the complete system of reps $\,0,1,\ldots, mn\!-\!1\,$ for integers $\!\bmod mn$.