Statement of Chinese Remainder Theorem; Proof of Uniqueness

The Chinese Remainder Theorem (CRT) states the following:

If $(m_1, m_2, ..., m_k)=1$, then the system of congruences: $$x\equiv a_1\pmod{m_1}$$ $$x\equiv a_2\pmod{m_2}$$ $$...$$ $$x\equiv a_k\pmod{m_k}$$ has exactly $1$ solution modulo $m_1m_2...m_k$.

The uniqueness part of CRT states that there is at most $1$ solution, and the existence part of CRT states that there is at least $1$ solution. Here, we will prove the uniqueness part, which is actually quite straightforward.

Let $X_1$ and $X_2$ be any $2$ solutions to the above system of congruences. Note that: $$X_1\equiv X_2\equiv a_1\pmod{m_1}$$ Thus, $m_1 \mid (X_1-X_2)$. By a similar reasoning, $m_i \mid (X_1-X_2)$ for all $1\le i\le k$. Therefore, if $[m_1, m_2, ..., m_k]$ denotes the least common multiple (LCM) of $m_1, m_2, ..., m_k$, then: $$[m_1, m_2, ..., m_k] \mid (X_1-X_2)$$ Since $m_1, m_2, ..., m_k$ are relatively prime, $[m_1, m_2, ..., m_k]=m_1m_2...m_k$. Therefore, $$m_1m_2...m_k \mid (X_1-X_2)$$ $$X_1\equiv X_2\pmod{m_1m_2...m_k}$$ This means that any two solutions must be congruent modulo $m_1m_2...m_k$. It follows that the system of congruences has at most $1$ solution modulo $m_1m_2...m_k$.

The Chinese remainder theorem is a theorem of number theory, which states that, if one knows the remainders of the division of an integer n by several integers, then one can determine uniquely the remainder of the division of n by the product of these integers, under the condition that the divisors are pairwise coprime.

The Chinese remainder theorem is widely used for computing with large integers, as it allows replacing a computation for which one knows a bound on the size of the result by several similar computations on small integers.