algebra911.com

Chinese Remainder Theorem

Ever faced a puzzle that felt like juggling multiple clues at once? The Chinese Remainder Theorem is a powerful mathematical tool for solving exactly that kind of problem. It helps you find a single number that satisfies several different remainder conditions simultaneously, a skill with surprising applications.

What Is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) is a principle from number theory that provides a way to find a unique solution to a system of simultaneous congruences, as long as their moduli are pairwise coprime. In simple terms, it's a method for finding a number that leaves specific remainders when divided by several different numbers.

Imagine you have a big bag of marbles. You don't know the total, but you know a few clues:

When you group the marbles into sets of 3, you have 2 left over.
When you group them into sets of 5, you have 3 left over.
When you group them into sets of 7, you have 2 left over.

How can you find the smallest possible number of marbles in the bag? This is exactly the kind of puzzle the Chinese Remainder Theorem was designed to solve. It takes multiple 'remainder' clues and combines them to find the single number that makes them all true.

What Are Congruences? A Quick Refresher

Before we can use the theorem, we need to be comfortable with the language it uses: congruences and modular arithmetic. You can think of modular arithmetic as "clock arithmetic." On a 12-hour clock, 15 hours after midnight is 3 o'clock. We can say that 15 is congruent to 3, modulo 12.

The notation we use is:

a \equiv b (\mod n)

This means that $a$ and $b$ have the same remainder when divided by $n$ . For example, $17 \equiv 2 (\mod 5)$ is a true statement because both 17 and 2 leave a remainder of 2 when divided by 5.

The Chinese Remainder Theorem solves a system of these congruences. A typical problem looks like this, where you need to find the unknown number $x$ :

x \equiv a_{1} (\mod n_{1})

x \equiv a_{2} (\mod n_{2})

⋮

x \equiv a_{k} (\mod n_{k})

There's one very important condition for the standard theorem to work: the moduli (the numbers you're dividing by, $n_{1}, n_{2}, \dots, n_{k}$ ) must be pairwise coprime. This just means that if you pick any two moduli from the list, their greatest common divisor (GCD) is 1. For example, 3, 5, and 7 are pairwise coprime because GCD(3,5)=1, GCD(3,7)=1, and GCD(5,7)=1.

How Does the Theorem Work with a Simple Case?

Let's build our intuition with a basic two-line problem. We want to find a number $x$ that satisfies both of these conditions:

x \equiv 2 (\mod 3)

x \equiv 1 (\mod 4)

Since the numbers are small, we can just list out possibilities for each line and see where they overlap.

Numbers that satisfy $x \equiv 2 (\mod 3)$ : 2, 5, 8, 11, 14, 17, ... (these are all 2 more than a multiple of 3).
Numbers that satisfy $x \equiv 1 (\mod 4)$ : 1, 5, 9, 13, 17, 21, ... (these are all 1 more than a multiple of 4).

Looking at our lists, we can see that 5 is the first number to appear in both. So, $x = 5$ is our smallest positive solution. The next number to appear in both is 17. Notice that $17 = 5 + 12$ . This isn't a coincidence! The solutions repeat every $3 \times 4 = 12$ numbers. This is the core idea of the theorem: there is a unique solution modulo the product of the moduli.

Example 1

Find the smallest positive integer $x$ that satisfies the system:

x \equiv 2 (\mod 3)

x \equiv 1 (\mod 4)

Solution by listing:

List numbers for the first congruence: The numbers that leave a remainder of 2 when divided by 3 are 2, 5, 8, 11, ...
Check these numbers against the second congruence:

Does 2 work? $2 \div 4$ has a remainder of 2. No, we need a remainder of 1.
Does 5 work? $5 \div 4$ has a remainder of 1. Yes!

The smallest positive integer solution is $x = 5$ .

This listing method is great for simple problems, but it quickly becomes impractical for larger numbers. For that, we need a systematic algorithm.

What Are the Steps to Solve Any System of Congruences?

Here is a reliable, step-by-step method to solve any system of congruences that meets the coprime condition. Let's use the general form from before:

x \equiv a_{1} (\mod n_{1})

x \equiv a_{2} (\mod n_{2})

⋮

x \equiv a_{k} (\mod n_{k})

Step 1: Check the Condition. Verify that all the moduli ( $n_{1}, n_{2}, \dots, n_{k}$ ) are pairwise coprime. If they aren't, this method won't work.
Step 2: Calculate the Big Modulus (N). Multiply all the individual moduli together to get one large product, $N$ . $N = n_{1} \times n_{2} \times \dots \times n_{k}$ This $N$ is the number after which the solutions will repeat.
Step 3: Calculate Partial Products (N_i). For each congruence $i$ , calculate $N_{i} = N / n_{i}$ . In other words, $N_{i}$ is the product of all moduli except for $n_{i}$ .
Step 4: Find the Modular Inverses (y_i). This is the most clever step. For each $i$ , you need to find a number $y_{i}$ that solves the congruence: $N_{i} y_{i} \equiv 1 (\mod n_{i})$ This $y_{i}$ is called the modular multiplicative inverse of $N_{i}$ modulo $n_{i}$ . For small numbers, you can find this by testing values for $y_{i}$ : 1, 2, 3, ... until you find one that works.
Step 5: Assemble the Solution (x_0). Now, you combine all the pieces you've found using one main formula. You multiply each remainder ( $a_{i}$ ), its partial product ( $N_{i}$ ), and its inverse ( $y_{i}$ ) together, and then sum up all these results.
$x_{0} = a_{1} N_{1} y_{1} + a_{2} N_{2} y_{2} + \dots + a_{k} N_{k} y_{k}$
Step 6: Find the Smallest Positive Solution. The number $x_{0}$ from Step 5 is a valid solution, but it might be very large. The general solution is any number congruent to $x_{0}$ modulo $N$ . To find the smallest positive solution, you simply calculate the remainder of $x_{0}$ when divided by $N$ . $x = x_{0} (\mod N)$ This final remainder is your answer.

A Fully Worked Example: Putting the Steps into Practice

Let's solve the marble problem from the introduction. We need to find the smallest positive integer $x$ such that:

x \equiv 2 (\mod 3)

x \equiv 3 (\mod 5)

x \equiv 2 (\mod 7)

Example 2

Solve the system of congruences above using the 6-step method.

Solution:

Step 1: Check the Condition. Our moduli are 3, 5, and 7. Since these are all prime numbers, they are automatically pairwise coprime. Check: GCD(3,5)=1, GCD(3,7)=1, GCD(5,7)=1. We can proceed.

Step 2: Calculate N. $N = 3 \times 5 \times 7 = 105$ . The solutions repeat every 105.

Step 3: Calculate N_i.

For $n_{1} = 3$ : $N_{1} = N / n_{1} = 105 / 3 = 35$ .
For $n_{2} = 5$ : $N_{2} = N / n_{2} = 105 / 5 = 21$ .
For $n_{3} = 7$ : $N_{3} = N / n_{3} = 105 / 7 = 15$ .

Step 4: Find Inverses y_i.

For $y_{1}$ : We need to solve $35 y_{1} \equiv 1 (\mod 3)$ . First, simplify $35 (\mod 3)$ . $35 = 11 \times 3 + 2$ , so the remainder is 2. The congruence becomes $2 y_{1} \equiv 1 (\mod 3)$ . Let's test values: If $y_{1} = 1$ , we get $2$ . If $y_{1} = 2$ , we get $4$ , and $4 \equiv 1 (\mod 3)$ . Perfect! So, $y_{1} = 2$ .
For $y_{2}$ : We need $21 y_{2} \equiv 1 (\mod 5)$ . Simplify $21 (\mod 5)$ . The remainder is 1. The congruence is $1 y_{2} \equiv 1 (\mod 5)$ . This is easy: $y_{2} = 1$ .
For $y_{3}$ : We need $15 y_{3} \equiv 1 (\mod 7)$ . Simplify $15 (\mod 7)$ . The remainder is 1. The congruence is $1 y_{3} \equiv 1 (\mod 7)$ . So, $y_{3} = 1$ .

Let's organize our findings in a table:

i	$a_{i}$	$n_{i}$	$N_{i}$	$y_{i}$
1	2	3	35	2
2	3	5	21	1
3	2	7	15	1

Step 5: Assemble the Solution. Using the formula $x_{0} = a_{1} N_{1} y_{1} + a_{2} N_{2} y_{2} + a_{3} N_{3} y_{3}$ : $x_{0} = (2) (35) (2) + (3) (21) (1) + (2) (15) (1)$ $x_{0} = 140 + 63 + 30$ $x_{0} = 233$

Step 6: Find the Smallest Positive Solution. We find the remainder of $x_{0}$ when divided by $N$ . $x = 233 (\mod 105)$ Since $233 = 2 \times 105 + 23$ , the remainder is 23.

The smallest number of marbles in the bag is 23.

Key formulas for chinese remainder theorem by Algebra911.

How to Solve an Ancient Word Problem with the CRT

The theorem gets its name from early appearances in Chinese mathematical texts. Here is a classic problem, paraphrased from the work of the mathematician Sun Tzu.

Example 3

An army has an unknown number of soldiers. When the general arranges them in columns of 3, there are 2 soldiers left over. When arranged in columns of 5, there are 3 left over. When arranged in columns of 7, there are 2 left over. What is the smallest possible number of soldiers in the army?

Wait, this is the same problem as the marbles! Yes, it is. The underlying math is identical. Let's try a different one.

New Problem: Find the smallest positive integer that leaves a remainder of 1 when divided by 2, 3, and 5, but is perfectly divisible by 7.

Solution:

First, translate the word problem into a system of congruences:

x \equiv 1 (\mod 2)

x \equiv 1 (\mod 3)

x \equiv 1 (\mod 5)

x \equiv 0 (\mod 7)

Step 1: Check Condition. The moduli are 2, 3, 5, and 7. All are prime numbers, so they are pairwise coprime.

Step 2: Calculate N. $N = 2 \times 3 \times 5 \times 7 = 210$ .

Step 3: Calculate N_i.

$N_{1} = 210 / 2 = 105$
$N_{2} = 210 / 3 = 70$
$N_{3} = 210 / 5 = 42$
$N_{4} = 210 / 7 = 30$

Step 4: Find Inverses y_i.

105y_1 \equiv 1 \pmod{2} \implies 1y_1 \equiv 1 \pmod{2} \implies y_1=1
70y_2 \equiv 1 \pmod{3} \implies 1y_2 \equiv 1 \pmod{3} \implies y_2=1
42y_3 \equiv 1 \pmod{5} \implies 2y_3 \equiv 1 \pmod{5} \implies y_3=3 (since $2 \times 3 = 6 \equiv 1$ )
30y_4 \equiv 1 \pmod{7} \implies 2y_4 \equiv 1 \pmod{7} \implies y_4=4 (since $2 \times 4 = 8 \equiv 1$ )

Step 5: Assemble the Solution. $x_{0} = a_{1} N_{1} y_{1} + a_{2} N_{2} y_{2} + a_{3} N_{3} y_{3} + a_{4} N_{4} y_{4}$ $x_{0} = (1) (105) (1) + (1) (70) (1) + (1) (42) (3) + (0) (30) (4)$ $x_{0} = 105 + 70 + 126 + 0$ $x_{0} = 301$

Step 6: Find the Smallest Positive Solution. $x = 301 (\mod 210)$ Since $301 = 1 \times 210 + 91$ , the remainder is 91.

The smallest such integer is 91. Let's check: 91 divided by 2, 3, or 5 leaves a remainder of 1. And $91 = 13 \times 7$ , so it's perfectly divisible by 7.

What Are Common Mistakes to Avoid?

The Chinese Remainder Theorem is a powerful algorithm, but it has several steps where it's easy to make a small error. Here are the most common pitfalls to watch out for:

Forgetting the Coprime Check. The very first step is crucial. If you try to apply this method when the moduli are not pairwise coprime (e.g., trying to solve a system with $(\mod 6)$ and $(\mod 4)$ ), you will not get a correct answer. A solution might not even exist.
Mixing Up $n_{i}$ and $N_{i}$ . Remember, $n_{i}$ is the original modulus from the problem statement. $N_{i}$ is the value you calculate by dividing the total product $N$ by $n_{i}$ . Keep your work organized in a table to avoid confusion.
Errors Finding the Inverse. Finding $y_{i}$ such that $N_{i} y_{i} \equiv 1 (\mod n_{i})$ can be tricky. Always double-check your inverse by multiplying it out. For example, in the last problem we found $y_{3} = 3$ for $n_{3} = 5$ . Check: $N_{3} y_{3} = 42 \times 3 = 126$ . Is $126 \equiv 1 (\mod 5)$ ? Yes, because 126 ends in a 6, so its remainder when divided by 5 is 1.
Forgetting the Final Modulo Step. The formula in Step 5 gives you a solution, but not necessarily the smallest positive one. Forgetting to calculate $x_{0} (\mod N)$ at the end is a very common mistake.
Simple Calculation Errors. There are many multiplications and additions involved. Take your time, write out each step, and use a calculator to check your arithmetic, especially for the large sum in Step 5.

Quick Summary and Reference

Here's a quick summary of the entire process for solving a system of congruences using the Chinese Remainder Theorem.

The Goal: Solve a system of congruences:

x \equiv a_{i} (\mod n_{i}) for i = 1, 2, \dots, k

The Condition: All moduli, $n_{i}$ , must be pairwise coprime.

The Algorithm:

Calculate the total product of the moduli: $N = n_{1} \times n_{2} \times \dots \times n_{k}$ .
For each congruence, calculate the partial product: $N_{i} = N / n_{i}$ .
For each congruence, find the modular inverse $y_{i}$ that solves $N_{i} y_{i} \equiv 1 (\mod n_{i})$ .
Calculate the preliminary solution, $x_{0}$ , using the main formula:
$x_{0} = \sum_{i = 1}^{k} a_{i} N_{i} y_{i} = a_{1} N_{1} y_{1} + a_{2} N_{2} y_{2} + \dots + a_{k} N_{k} y_{k}$
Find the smallest positive solution, $x$ , by taking the result modulo $N$ : $x = x_{0} (\mod N)$ .

Frequently Asked Questions

What is the Chinese Remainder Theorem actually used for in the real world?

It's crucial in modern cryptography, especially in the RSA algorithm, for speeding up complex calculations with large numbers. It's also used in computer science for algorithms that handle huge integers and in coding theory for creating error-correcting codes.

What happens if the moduli are not coprime?

The standard theorem doesn't apply directly, but a solution might still exist. You have to use a more advanced, generalized version of the theorem that first checks for contradictions between the congruences (for example, $x \equiv 1 (\mod 4)$ and $x \equiv 2 (\mod 2)$ is impossible).

Where does the name 'Chinese Remainder Theorem' come from?

The earliest known statement of this type of problem appeared in the 3rd-century book 'Sunzi Suanjing' (The Mathematical Classic of Sun Zi) by the Chinese mathematician Sun Tzu. The full algorithm for solving it was later generalized by other mathematicians.

Is the solution always a single number?

The solution is a whole family of numbers. The theorem gives you the unique smallest positive solution, but any number you get by adding or subtracting multiples of the big modulus $N$ will also satisfy the system.

What does 'pairwise coprime' mean again?

It means if you take any two different moduli from your list, their greatest common divisor is 1. For example, in the set {6, 7, 25}, they are pairwise coprime because GCD(6,7)=1, GCD(6,25)=1, and GCD(7,25)=1.

Is there an easier way to find the modular inverse?

For the small numbers you see in class, trial and error (testing y=1, 2, 3...) is often the fastest way. For larger numbers, there is a more systematic method called the Extended Euclidean Algorithm, which is a topic you might learn in a more advanced number theory or discrete math class.

Can I solve these problems by just listing out multiples?

Yes, for very small numbers, that can be a good way to understand the problem and find the answer. However, the CRT provides a systematic method that works for any numbers, no matter how large, which is much more powerful and efficient than guessing or listing.