Chinese Remainder Theorem

Curtis Clement, Satvik Golechha, Agnishom Chattopadhyay, and contributed

The Chinese Remainder Theorem is a theorem which gives a unique solution to simultaneous linear congruences with coprime moduli. In its basic form, the Chinese remainder theorem will determine a number \(p\) that, when divided by some given divisors, leaves given remainders.

Theorem And Proof
Applications
See Also

Theorem And Proof

Chinese Remainder Theorem

Given pairwise coprime positive integers \( n_1, n_2, \ldots n_k\) and arbitrary integers \(a_1, a_2, \ldots a_k\), the system of simultaneous congruences

\[\begin{align} x &\equiv a_1 \bmod{n_1}\\ x &\equiv a_2 \bmod{n_2}\\ & \vdots\\ x &\equiv a_k \bmod{n_k} \end{align}\]

has a solution, and the solution is unique modulo \(N = n_1n_2\ldots n_k\).

The following is a general construction to find a solution to a system of congruences using the Chinese Remainder Theorem.

Compute \(N = n_1 \times n_2 \times \cdots \times n_k\)
For each \(i = 1 \ldots k\), compute \[y_i = \frac{N}{n_i} = n_1n_2 \ldots n_{i-1}n_{i+1} \ldots n_k\]
For each \( i = 1\ldots k\), compute \(z_i \equiv y_i^{-1} \bmod{n_i}\) using Euclid's extended algorithm (\(z_i\) exists since \(n_1, n_2, \ldots n_k\) are pairwise coprime).
The integer \( x = \sum_{i=1}^{k} a_i y_i z_i \) is a solution to the system of congruences, and \(x \bmod{N} \) is the unique solution modulo \(N\).

Proof: To see why \(x\) is a solution, for each \(i = 1, 2, \ldots k\), we have

\[\begin{align} x \bmod{n_i} & \equiv ( a_1 y_1 z_1 + a_2y_2z_2 + \ldots a_k y_k z_k) \bmod{n_i}\\ & \equiv a_i y_i z_i \bmod{n_i} \\ & \equiv a_i \bmod{n_i} , \end{align}\]

where the second line follows since \(y_j \equiv 0 \bmod{n_i}\) for each \(j \neq i \), and the third line follows since \(y_i z_i \equiv 1 \bmod{n_i}\).

Now, suppose there are two solutions \(u\) and \(v\) to the system of congruences. Then \(n_1 \lvert (u -v), n_2 \lvert (u-v) \ldots n_k \lvert (u-v)\), and since \(n_1, n_2, \ldots n_k\) are relatively prime, we have \(n_1n_2\ldots n_k \) divides \(u-v\), or \[u \equiv v \bmod{n_1n_2\ldots n_k} .\] Thus, the solution is unique modulo \(n_1n_2\ldots n_k\). \(_\square\)

Applications

The Chinese remainder theorem often allows us to reduce a question involving modulus \(n = p_1^{\alpha_1} p_2^{\alpha_2} \ldots p_l^{\alpha_l}\) into a question for the prime power moduli \(p_i^{\alpha_i}\).

The real life application of the Chinese Remainder Theorem might be of interest to the reader, so we will give one such example here. One use is in astronomy where k events may occur regularly, with periods \(n_{1}\), \(n_{2}\),... \(n_{k}\) and with the \({i}\)-th event happening at times \({x}\) = \(a_{i}\), \(a_{i}\) + \(n_{i}\), \(a_{i}\) + 2\(n_{i}\),....This means that the k-events occur simultaneously at time \({x}\) where \({x}\) = \(a_{i}\) mod(\(n_{i}\)) for all \({i}\). A simple illustration of this is the orbit of planets and moons, as well as eclipses.

What are the last two digits of \(49^{19}?\)

Solution: Observe that \(100 = 25 \times 4\) and \(\gcd(25,4) = 1\). Then by the Chinese remainder theorem, the value \(x \equiv 49^{19} \pmod{100}\) is in correspondence with the solutions to the simultaneous congruences

\[\begin{align} x \equiv 49^{19} &\pmod{25}\\ x \equiv 49^{19} &\pmod{4}. \end{align}\]

Now,

\[49^{19} \equiv (-1)^{19} \pmod{25} \equiv -1 \pmod{25}\] \[49^{19} \equiv (1)^{19} \pmod{4} \equiv 1 \pmod{4}\]

Then the Chinese Remainder Theorem gives the value

\[\begin{align} x &\equiv ((-1)(4)(19) + (1)(25)(1)) \pmod{100}\\ & \equiv ( -76 + 25) \pmod{100}\\ & \equiv -51 \pmod{100}\\ &\equiv 49 \pmod{100}. \end{align}\]

Therefore, the last two digits of \(49^{19}\) are 49. Note that the above system of congruences is obtained for any odd exponent of 49, so the solution using the Chinese Remainder theorem also gives that the last two digits of \(49^k\) are 49 for any positive odd value of \(k\).

Does the system of congruences \[ \begin{align} x & \equiv 1 \bmod{4}\\ x &\equiv 2 \bmod{6}\\ x & \equiv 3 \bmod{7} \end{align}\] have a solution?

Solution: Note that the Chinese Remainder Theorem does not apply here, since the moduli are not pairwise coprime (in particular, \( \gcd(4,6) = 2 > 1\)). If \(x\) is a solution to the system of congruences, then the first congruence implies \(x\) is odd and the second congruence implies \(x\) is even. This is a contradiction, and therefore, the system has no solution.

Show that there exists \(99\) consecutive integers \(a_1, a_2, \ldots a_{99}\) such that each \(a_i\) is divisible by the cube of some integer greater than 1.

Solution: Let \(p_1, p_2, \ldots p_{99}\) be distinct prime numbers. Consider the simultaneous congruences

\[ \begin{align} x & \equiv -1 \bmod{p_1^3}\\ x & \equiv -2 \bmod{p_2^3}\\ & \cdots\\ x & \equiv -99 \bmod{p_{99}^3}.\\ \end{align}\]

Since \(p_i\) are pairwise coprime, this system of equations has a solution by the Chinese Remainder Theorem. Then the integers \(a_i = x+i\) for \(i = 1,2 \ldots 99\) are 99 consecutive integers such that \(p_i^3 \) divides \(a_i\).

Explorations

Topics

Chinese Remainder Theorem

Quiz

Relevant For...

Contents