# Chinese Remainder Theorem

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

Chinese Remainder TheoremGiven 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 \pmod{n_1}\\ x &\equiv a_2 \pmod{n_2}\\ & \vdots\\ x &\equiv a_k \pmod{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, 2,\ldots, k\), compute \[y_i = \frac{N}{n_i} = n_1n_2 \cdots n_{i-1}n_{i+1} \cdots n_k.\]

For each \( i = 1,2,\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 \pmod{n_i} & \equiv ( a_1 y_1 z_1 + a_2y_2z_2 + \cdots+ a_k y_k z_k) \pmod{n_i}\\ & \equiv a_i y_i z_i \pmod{n_i} \\ & \equiv a_i \pmod{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 that \(n_1n_2\cdots n_k \) divides \(u-v\), or

\[u \equiv v \pmod{n_1n_2\cdots n_k} .\]

Thus, the solution is unique modulo \(n_1n_2\cdots n_k\). \(_\square\)

## Alternate Process

When a system contains a relatively small number of congruences, an efficient process exists to apply the Chinese Remainder Theorem.

Solve the system of congruences:

\[\begin{cases}\begin{align} x &\equiv 1 \pmod{3} \\ x &\equiv 4 \pmod{5} \\ x &\equiv 6 \pmod{7}. \end{align}\end{cases}\]

Begin with the congruence with the largest modulus, \(x \equiv 6 \pmod{7}.\) Rewrite this congruence as an equivalent equation:

\[x=7j+6, \text{ for some integer }j.\]

Substitute this expression for \(x\) into the congruence with the next largest modulus:

\[x \equiv 4 \pmod{5} \implies 7j+6 \equiv 4 \pmod{5}.\]

Then solve this congruence for \(j:\)

\[j \equiv 4 \pmod{5}\]

Rewrite this congruence as an equivalent equation:

\[j=5k+4, \text{ for some integer k.}\]

Substitute this expression for \(j\) into the expression for \(x:\)

\[\begin{align} x &= 7(5k+4)+6 \\ x &= 35k+34. \\ \end{align}\]

Now substitute this expression for \(x\) into the final congruence, and solve the congruence for \(k:\)

\[\begin{align} 35k+34 &\equiv 1 \pmod{3} \\ k &\equiv 0 \pmod{3}. \end{align}\]

Write this congruence as an equation, then substitute the expression for \(k\) into the expression for \(x:\)

\[\begin{align} k &= 3l, \text{ for some integer }l. \\ x &= 35(3l)+34 \\ x &= 105l+34 \end{align}\]

This equation implies the congruence:

\[x \equiv 34 \pmod{105}\]

This happens to be the solution to the system of congruences.\(\ _\square\)

Alternate Process for Chinese Remainder TheoremFor a system of congruences with co-prime moduli,

Begin with the congruence with the largest modulus, \(x \equiv a_k \pmod{n_k}.\) Re-write this modulus as an equation, \(x=n_kj_k+a_k,\) for some positive integer \(j_k.\)

Substitute the expression for \(x\) into the congruence with the next largest modulus, \(x \equiv a_k \pmod{n_k} \implies n_kj_k+a_k \equiv a_{k-1} \pmod{n_{k-1}}.\)

Solve this congruence for \(j_k.\)

Write the solved congruence as an equation, then substitute this expression for \(j_k\) into the equation for \(x.\)

Continue substituting and solving congruences until the equation for \(x\) implies the solution to the system of congruences.

You are building a rainbow building from \(N\) cubic unit blocks.

First, you put 3 cubes each to form a group of columns and discard the remaining cubes away.

Then, you put 5 columns together each to form a group of \(3\times 5\) cubic bases and discard the remaining columns away as before.

Finally, you stack 7 bases over one another to build a desired \(3\times 5\times 7\) cuboid structure each, as shown above, and discard all the other bases away as usual.

If there are a total of 52 discarded cubes, and \(N\) is a multiple of 11, what is the least possible value of \(N\)?

The Chinese Remainder Theorem can be applied to systems with moduli that are not co-prime, but a solution to such a system does not always exist.

Solve the system of congruences:

\[\begin{cases}\begin{align} x &\equiv 5 \pmod{6} \\ x &\equiv 3 \pmod{8}. \\ \end{align}\end{cases}\]

Note that the greatest common divisor of the moduli is 2. The first congruence implies \(x \equiv 1\pmod {2}\) and the second congruence also implies \(x \equiv 1 \pmod{2}.\) Therefore, there is no conflict between these two congruences. In fact, the system of congruences can be reduced to a simpler system of congruences by dividing out the GCD of the moduli from the modulus of the first congruence:

\[\begin{cases}\begin{align} x &\equiv 2 \pmod{3} \\ x &\equiv 3 \pmod{8}. \\ \end{align}\end{cases}\]

Write the second congruence as an equation:

\[x=8j+3.\]

Substitute into the first congruence and solve for \(j:\)

\[\begin{align} 8j+3 &\equiv 2 \pmod{3} \\ j &\equiv 1 \pmod{3}. \end{align}\]

Write this congruence as an equation, then substitute into the equation for \(x:\)

\[\begin{align} j &= 3k+1 \\ x &= 8(3k+1)+3 \\ x &= 24k+11. \end{align}\]

This gives \(x \equiv 11 \pmod{24}\) as the solution to the system of congruences. Note that \(\text{lcm}(6,8)=24.\)

Whether or not a system of congruences has solutions depends on if there are any conflicts between pairs of congruences.

Show that there are no solutions to the system of congruences:

\[\begin{cases}\begin{align} x &\equiv 2 \pmod{6} \\ x &\equiv 5 \pmod{9} \\ x &\equiv 7 \pmod{15}. \end{align}\end{cases}\]

Note that each modulus is divisible by 3. The first and second congruences imply that \(x \equiv 2 \pmod{3}.\) However, the third congruence implies that \(x \equiv 1 \pmod{3}.\) Since these both cannot be true, there are no solutions to the system of congruences.

A system of linear congruences has solutions if and only if for every pair of congruences within the system,

\[\begin{cases}\begin{align} x &\equiv a_i \pmod{n_i} \\ x &\equiv a_j \pmod{n_j}, \end{align}\end{cases}\]

\[a_i \equiv a_j \pmod{\gcd(n_i,n_j)}.\]

Furthermore, if solutions exist, then they are of the form:

\[x \equiv b \pmod{\text{lcm}(n_1,n_2, \ldots , n_k)}\]

for some integer \(b.\)

Brahmagupta has a basket full of eggs. When he takes the eggs out of the basket 2 at a time, there is 1 egg left over. When he takes them out 3 at a time, there are 2 eggs left over. Likewise, when he takes the eggs out 4, 5, and 6 at a time, he finds remainders of 3, 4, and 5, respectively. However, when he takes the eggs out 7 at a time, there are no eggs left over.

What is the least amount of eggs that could be in Brahmagupta's basket?

## 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}, \ldots, n_{k}\) and with the \(i^\text{th}\) event happening at times \(x = a_i, a_i+n_i, a_i+2n_i, \ldots.\) This means that the \(k\) events occur simultaneously at time \(x,\) where \(x = a_i \bmod{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}?\)

Observe that \(100 = 25 \times 4\) and \(\gcd(25,4) = 1\). Then by the Chinese remainder theorem, the value \(x \equiv 49^{19} \bmod{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,

\[\begin{align} 49^{19} \equiv (-1)^{19} \pmod{25} &\equiv -1 \pmod{25}\\ 49^{19} \equiv (1)^{19} \pmod{4} &\equiv 1 \pmod{4}. \end{align}\]

Then the Chinese remainder theorem gives the value

\[\begin{align} x &\equiv \big((-1)(4)(19) + (1)(25)(1)\big) \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\). \(_\square\)

Does the system of congruences

\[ \begin{align} x & \equiv 1 \pmod{4}\\ x &\equiv 2 \pmod{6}\\ x & \equiv 3 \pmod{7} \end{align}\]

have a solution?

Notice that the divisors are 4, 6 and 7. Since these triplets are not pairwise coprime \((\)in particular, \(\gcd(4,6)\ne1)\), we can't apply Chinese remainder theorem yet. By breaking up the second linear congruence, we obtain

\[ \begin{cases} x\equiv 0 \pmod2 \\ x \equiv 2 \pmod 3 . \end{cases} \]

Interpreting \(x \equiv 0 \pmod 2 \) tells us that \(x\) is even. However, interpreting the original congruence \(x \equiv 1 \pmod 4 \) tells us that \(x\) is odd. This means that \(x\) is both odd and even, which is a contradiction. Hence, there is no solution.

Alternatively, one can directly interpret from the first and second congruence that \(x\) is odd and even, respectively, which is absurd. Therefore, the system has no solution. \(_\square\)

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.

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

\[ \begin{align} x & \equiv -1 \pmod{p_1^3}\\ x & \equiv -2 \pmod{p_2^3}\\ & \vdots\\ x & \equiv -99 \pmod{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\). \(_\square\)

Four friends--let's call them A, B, C, and D--are planning to go to the concert, but they realize that they are a few dollars short to buy the tickets ($50 per ticket).

We know that each of them has an integer amount of dollars and that

If \(B\) borrowed $\(1\) from \(A\), then \(B\) would have \(\frac{2}{3}\) of \(A\)'s balance;

If \(C\) borrowed $\(2\) from \(B\), then \(C\) would have \(\frac{3}{5}\) of \(B\)'s balance;

If \(D\) borrowed $\(3\) from \(C\), then \(D\) would have \(\frac{5}{7}\) of \(C\)'s balance.

At least how much more money (in $) do they need all together in order to afford 4 tickets?

A Chinese general counts the number of surviving soldiers of a battle by aligning them successively in rows of certain sizes. Each time, he counts the number of remaining soldiers who failed to fill a row. The general initially had 1200 soldiers before the battle; after the battle

- aligning them in rows of 5 soldiers leaves 3 remaining soldiers;
- aligning them in rows of 6 soldiers leaves 3 remaining soldiers;
- aligning them in rows of 7 soldiers leaves 1 remaining soldier;
- aligning them in rows of 11 soldiers leaves 0 remaining soldiers.

How many soldiers survived the battle?

A box contains gold coins.

If the coins are equally divided among six friends, four coins are left over.

If the coins are equally divided among five friends, three coins are left over.

If the box holds the smallest number of coins that meets these two conditions, how many coins are left when equally divided among seven friends?

## See Also

**Cite as:**Chinese Remainder Theorem.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/chinese-remainder-theorem/