The Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a fundamental result in number theory that allows us to solve a system of simultaneous congruences with pairwise relatively prime moduli.

Statement of the Theorem

Let $m_1, m_2, \dots, m_n$ be pairwise relatively prime positive integers and let $a_1, a_2, \dots, a_n$ be any integers. Then the system of congruences

has a unique solution modulo $M = m_1m_2\cdots m_n$.

Proof of the Theorem

The proof of CRT can be divided into two parts. First, we show that the system of congruences has a solution. Second, we show that the solution is unique modulo $M$.

Existence of a Solution

Let $M_i = M/m_i$ for $i=1,2,\dots,n$. Since $m_i$ and $M_i$ are relatively prime, there exists an integer $N_i$ such that $M_iN_i \equiv 1 \pmod{m_i}$. Let $x$ be the integer defined by

We claim that $x$ is a solution to the system of congruences. To see this, we compute

Therefore, $x$ satisfies each congruence in the system.

Uniqueness of the Solution

Suppose that $x_1$ and $x_2$ are two solutions to the system of congruences. Then we have

Therefore, the two solutions are congruent modulo $M$. Hence, the solution is unique modulo $M$.

Applications of the Theorem

The Chinese Remainder Theorem has numerous applications in number theory, computer science, cryptography, and other fields. For example, it is used in the Chinese remainder algorithm for computing large powers of integers, in the RSA cryptosystem, in error-correcting codes, and in the construction of finite fields.

Conclusion

The Chinese Remainder Theorem is a powerful tool in number theory that allows us to solve a system of simultaneous congruences with pairwise relatively prime moduli. It has many applications in various fields, and its elegant proof highlights the beauty of number theory.

Links

中国剰余定理[JA]