Discrete Math · Undergraduate
The Chinese Remainder Theorem
Quick answer
Find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7. The Chinese remainder theorem says such a system of congruences has exactly one solution modulo the product of the moduli, as long as the moduli share no common factors. Here the answer is 23 modulo 105. The solution can be built from modular inverses, or found one congruence at a time. When the moduli share a factor, the system may have no solution at all.
What you'll learn
- State the Chinese remainder theorem
- Solve a system of congruences by substitution
- Build the solution with modular inverses
- Decide when a system with non-coprime moduli has a solution
Several remainders at once
An ancient puzzle asks for a number with remainder on division by , remainder on division by , and remainder on division by . In modular arithmetic:
The Chinese remainder theorem. If the moduli are pairwise coprime, so no two share a factor greater than , the system has exactly one solution modulo their product. Here that product is , and the solution is .
Why there is exactly one solution
Consider the remainders of on division by , and . If two of these numbers had the same three remainders, their difference would be divisible by , and , and so by , since the moduli share no factors. That is impossible for two different numbers below . So the numbers give different triples of remainders, and there are exactly possible triples: each triple occurs exactly once. Counting proves the solution exists and is unique.
Worked examples
Common mistakes
Practice problems
-
Solve , .
Answer
Full solution
; gives , so and .
-
Solve , .
Answer
Full solution
; gives , so .
-
Solve , , .
Answer
Full solution
is odd, and .
-
Eggs taken out , , , or at a time leave ; taken out at a time they leave . What is the smallest number of eggs?
Answer
Full solution
(the lcm of to ) and . Try : .
-
Does , have a solution?
Answer
No
Full solution
Modulo , the first gives and the second .
-
In Example 2, why is congruent to mod and mod ?
Answer
is a multiple of and of .
Full solution
Each is the product of the other moduli, so its term vanishes modulo them.
-
How many integers from to satisfy and , with no condition mod ?
Answer
Full solution
The pair fixes modulo , and contains blocks of .
-
A student solves as . What should they do instead?
Answer
Multiply by the inverse of mod , which is : .
Full solution
Fractions are not residues; the inverse comes from .
Frequently asked questions
What does the Chinese remainder theorem say?
If m₁, …, mₖ are pairwise coprime, the system x ≡ aᵢ (mod mᵢ) has exactly one solution modulo M = m₁m₂⋯mₖ.
How do you solve a system of two congruences?
Write the first as x = a₁ + m₁t, substitute into the second, and solve the resulting congruence for t with a modular inverse.
What is the inverse construction?
With Mᵢ = M/mᵢ and yᵢ the inverse of Mᵢ mod mᵢ, the solution is x = Σ aᵢMᵢyᵢ reduced mod M.
What if the moduli are not coprime?
The system has a solution only if the congruences agree modulo the gcd of each pair. Then the solution is unique modulo the lcm.
Where does the name come from?
The problem appears in the Sunzi Suanjing, a Chinese text from around the 3rd to 5th century, with the very example 2, 3, 2 mod 3, 5, 7.