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 22 on division by 33, remainder 33 on division by 55, and remainder 22 on division by 77. In modular arithmetic:

x≡2(mod3)x≡3(mod5)x≡2(mod7)x \equiv 2 \pmod 3 \qquad x \equiv 3 \pmod 5 \qquad x \equiv 2 \pmod 7

The Chinese remainder theorem. If the moduli are pairwise coprime, so no two share a factor greater than 11, the system has exactly one solution modulo their product. Here that product is 105105, and the solution is x≡23x \equiv 23.

Why there is exactly one solution

Consider the remainders of 0,1,2,…,1040, 1, 2, \ldots, 104 on division by 33, 55 and 77. If two of these numbers had the same three remainders, their difference would be divisible by 33, 55 and 77, and so by 105105, since the moduli share no factors. That is impossible for two different numbers below 105105. So the 105105 numbers give 105105 different triples of remainders, and there are exactly 3⋅5⋅7=1053 \cdot 5 \cdot 7 = 105 possible triples: each triple occurs exactly once. Counting proves the solution exists and is unique.

Worked examples

Common mistakes

Practice problems

  1. Solve x≡3(mod4)x \equiv 3 \pmod 4, x≡4(mod5)x \equiv 4 \pmod 5.

    Answer

    x≡19(mod20)x \equiv 19 \pmod{20}

    Full solution

    x=3+4tx = 3 + 4t; 3+4t≡4(mod5)3 + 4t \equiv 4 \pmod 5 gives 4t≡14t \equiv 1, so t≡4t \equiv 4 and x=19x = 19.

  2. Solve x≡1(mod4)x \equiv 1 \pmod 4, x≡2(mod9)x \equiv 2 \pmod 9.

    Answer

    x≡29(mod36)x \equiv 29 \pmod{36}

    Full solution

    x=2+9tx = 2 + 9t; 2+9t≡1(mod4)2 + 9t \equiv 1 \pmod 4 gives t≡−1≡3t \equiv -1 \equiv 3, so x=29x = 29.

  3. Solve x≡1(mod2)x \equiv 1 \pmod 2, x≡2(mod3)x \equiv 2 \pmod 3, x≡3(mod5)x \equiv 3 \pmod 5.

    Answer

    x≡23(mod30)x \equiv 23 \pmod{30}

    Full solution

    2323 is odd, 23=7⋅3+223 = 7 \cdot 3 + 2 and 23=4⋅5+323 = 4 \cdot 5 + 3.

  4. Eggs taken out 22, 33, 44, 55 or 66 at a time leave 11; taken out 77 at a time they leave 00. What is the smallest number of eggs?

    Answer

    301301

    Full solution

    x≡1(mod60)x \equiv 1 \pmod{60} (the lcm of 22 to 66) and x≡0(mod7)x \equiv 0 \pmod 7. Try 61,121,181,241,30161, 121, 181, 241, 301: 301=7⋅43301 = 7 \cdot 43.

  5. Does x≡2(mod6)x \equiv 2 \pmod 6, x≡3(mod9)x \equiv 3 \pmod 9 have a solution?

    Answer

    No

    Full solution

    Modulo gcd⁡(6,9)=3\gcd(6, 9) = 3, the first gives x≡2x \equiv 2 and the second x≡0x \equiv 0.

  6. In Example 2, why is M1y1=70M_1y_1 = 70 congruent to 00 mod 55 and mod 77?

    Answer

    M1=35M_1 = 35 is a multiple of 55 and of 77.

    Full solution

    Each MiM_i is the product of the other moduli, so its term vanishes modulo them.

  7. How many integers from 00 to 104104 satisfy x≡2(mod3)x \equiv 2 \pmod 3 and x≡3(mod5)x \equiv 3 \pmod 5, with no condition mod 77?

    Answer

    77

    Full solution

    The pair fixes xx modulo 1515, and 105105 contains 77 blocks of 1515.

  8. A student solves 3t≡1(mod5)3t \equiv 1 \pmod 5 as t=13t = \tfrac{1}{3}. What should they do instead?

    Answer

    Multiply by the inverse of 33 mod 55, which is 22: t≡2t \equiv 2.

    Full solution

    Fractions are not residues; the inverse comes from 3⋅2=6≡13 \cdot 2 = 6 \equiv 1.

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.

What to learn next