# 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.

#### Contents

## 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 \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\)

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\)?

## 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\).

- Aligning them in rows of 5 soldiers, remained 3 soldiers;
- Aligning them in rows of 6 soldiers, remained 3 soldiers;
- Aligning them in rows of 7 soldiers, remained 1 soldier;
- Aligning them in rows of 11 soldiers, remained 0 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/