Chinese Remainder Theorem: Step-by-Step Examples and Solutions

The Chinese Remainder Theorem finds a number from its remainders. Given a set of congruences with moduli that share no common factors, it guarantees exactly one solution modulo the product of those moduli, and it tells you how to build that solution. A number leaving 1 on division by 4 and 3 on division by 5 must be congruent to 13 modulo 20.

The theorem answers a question that ordinary division cannot: not “what is the remainder of this number”, but “which number has these remainders”. It turns several small facts into one exact answer.

This guide teaches three methods, from the one you can do in your head to the one that scales, works each through with verification, handles moduli that do share factors, and ends with eight practice problems and answers.

The Problem the Theorem Solves

A single congruence pins a number down only loosely. The statement

x ≡ 3 (mod 7)

is satisfied by 3, 10, 17, 24, 31 and infinitely many others. Adding a second condition narrows things sharply:

x ≡ 3  (mod 7)
x ≡ 5  (mod 11)

Now only one value in every 77 works. The Chinese Remainder Theorem says that is always the case, provided the moduli are pairwise coprime, meaning every pair of them has a greatest common divisor of 1.

Chinese Remainder Theorem. If m₁, m₂, …, m_k are pairwise coprime, then the system x ≡ r₁ (mod m₁), …, x ≡ r_k (mod m_k) has a solution, and that solution is unique modulo M = m₁ · m₂ · … · m_k.

Two claims are packed in there. Existence: a solution always exists, whatever the remainders happen to be. Uniqueness: there is only one solution in each block of M consecutive integers, so once you find it you have found them all.

The name comes from a problem in the Sunzi Suanjing, a Chinese mathematical text from roughly the third to fifth century, which asks for a number leaving 2 on division by 3, 3 on division by 5 and 2 on division by 7. The answer is 23, and the Chinese Remainder Theorem Calculator solves that system and any other one step by step.

If congruence notation itself is unfamiliar, the foundations are in modular arithmetic explained.

Checking the Moduli First

Before any method runs, test the moduli. Pairwise coprime means every pair, not just the set as a whole.

The set 2, 3, 4 is the instructive one. Two of the three pairs are fine, and the single bad pair is enough to put the standard theorem out of reach. That case is not hopeless, and it is handled further down.

Method 1: The Sieve

For small moduli, listing candidates is fastest and needs no theory at all.

Problem. Solve x ≡ 1 (mod 4) and x ≡ 3 (mod 5).

Step 1. List the numbers satisfying the congruence with the larger modulus, since that list grows more slowly:

x ≡ 3 (mod 5):   3, 8, 13, 18, 23, 28, …

Step 2. Test each against the other congruence until one passes:

3  ÷ 4 → remainder 3    ✗
8  ÷ 4 → remainder 0    ✗
13 ÷ 4 → remainder 1    ✓

Step 3. State the answer modulo the product. Here M = 4 × 5 = 20:

x ≡ 13 (mod 20)

Verification. 13 = 4 × 3 + 1 ✓ and 13 = 5 × 2 + 3 ✓.

The full solution set is 13, 33, 53, 73 and so on, plus −7, −27 going backwards. The theorem’s uniqueness claim is what lets you stop searching after the first hit.

The sieve is reliable but slows down quickly. With moduli 5, 7 and 9 you could be testing 315 candidates.

Method 2: Substitution

This method scales properly and is the one worth learning. It converts a congruence into an equation, substitutes, and solves.

Problem. Solve x ≡ 3 (mod 7) and x ≡ 5 (mod 11).

Step 1: Turn the first congruence into an equation. Saying x leaves 3 on division by 7 is the same as saying:

x = 3 + 7t          for some whole number t

Step 2: Substitute into the second congruence.

3 + 7t ≡ 5 (mod 11)
    7t ≡ 2 (mod 11)

Step 3: Solve for t. This needs the inverse of 7 modulo 11, the number that turns 7 into 1. Testing multiples of 7: 7 × 8 = 56 = 55 + 1, so 56 ≡ 1 (mod 11) and the inverse is 8.

Multiply both sides by 8:

8 × 7t ≡ 8 × 2  (mod 11)
    56t ≡ 16    (mod 11)
      t ≡ 5     (mod 11)

Step 4: Substitute back. Taking t = 5:

x = 3 + 7 × 5 = 38

Answer. x ≡ 38 (mod 77).

Verification. 38 = 7 × 5 + 3 ✓ and 38 = 11 × 3 + 5 ✓.

Only one modular inverse was needed here, and it was small enough to find by inspection. For larger moduli, the systematic tool is the extended Euclidean algorithm, and the methods for finding any inverse are collected in modular inverse.

Extending to three congruences

Substitution handles longer systems by merging two at a time. Each merge replaces two congruences with one, so a three-congruence system becomes a two-congruence system, then a single answer. The modulus of each merged congruence is the product of the two that went into it.

Method 3: The Construction Formula

The formula builds the answer directly rather than searching or substituting. It is the version that generalises, and the version a computer uses.

M   = m₁ · m₂ · … · m_k          the product of every modulus
Mᵢ  = M / mᵢ                      everything except mᵢ
yᵢ  = the inverse of Mᵢ modulo mᵢ
x   = Σ rᵢ · Mᵢ · yᵢ   (mod M)

Why it works. Look at one term, rᵢ · Mᵢ · yᵢ. Because Mᵢ contains every modulus except mᵢ as a factor, that term is divisible by all the others, so it contributes 0 to every congruence but the i-th. Against mᵢ itself, Mᵢ · yᵢ ≡ 1 by the definition of the inverse, so the term contributes exactly rᵢ. Adding the terms therefore satisfies every congruence at once.

Problem. Solve x ≡ 2 (mod 5), x ≡ 3 (mod 7), x ≡ 4 (mod 9).

Step 1: Check the moduli. gcd(5, 7) = gcd(5, 9) = gcd(7, 9) = 1. Pairwise coprime. ✓

Step 2: Compute M and each Mᵢ.

M  = 5 × 7 × 9 = 315
M₁ = 315 / 5 = 63
M₂ = 315 / 7 = 45
M₃ = 315 / 9 = 35

Step 3: Find each inverse. Reduce Mᵢ modulo mᵢ first, which keeps the numbers tiny:

63 ≡ 3 (mod 5)    and    3 × 2 = 6 ≡ 1 (mod 5)     so  y₁ = 2
45 ≡ 3 (mod 7)    and    3 × 5 = 15 ≡ 1 (mod 7)    so  y₂ = 5
35 ≡ 8 (mod 9)    and    8 × 8 = 64 ≡ 1 (mod 9)    so  y₃ = 8

Step 4: Assemble the table and sum.

Step 5: Reduce modulo M.

2047 = 315 × 6 + 157

Answer. x ≡ 157 (mod 315).

Verification against all three congruences:

157 = 5 × 31 + 2     ✓
157 = 7 × 22 + 3     ✓
157 = 9 × 17 + 4     ✓

Which Method to Use

For exam work, substitution is usually the safest choice: the numbers stay small and every step is checkable.

When the Moduli Are Not Coprime

The classical theorem does not apply, but the system may still be solvable. The exact condition is weaker:

A system is solvable if and only if rᵢ ≡ rⱼ (mod gcd(mᵢ, mⱼ)) for every pair. The solution is then unique modulo lcm(m₁, …, m_k).

This collapses to the usual statement when the moduli are coprime, since a gcd of 1 makes every pair agree automatically and the lcm equals the product.

A solvable non-coprime system

Problem. Solve x ≡ 5 (mod 8) and x ≡ 9 (mod 12).

Compatibility check. gcd(8, 12) = 4. Reduce both remainders modulo 4:

5 mod 4 = 1
9 mod 4 = 1        they agree, so a solution exists

Solve by substitution. Write x = 5 + 8t and substitute:

5 + 8t ≡ 9  (mod 12)
    8t ≡ 4  (mod 12)

Every term here is divisible by 4, so divide the whole congruence through, including the modulus:

2t ≡ 1 (mod 3)

The inverse of 2 modulo 3 is 2, since 2 × 2 = 4 ≡ 1. So t ≡ 2 (mod 3), and taking t = 2:

x = 5 + 8 × 2 = 21

Answer. x ≡ 21 (mod 24), since lcm(8, 12) = 24, not 96.

Verification. 21 = 8 × 2 + 5 ✓ and 21 = 12 × 1 + 9 ✓.

Note the modulus of the answer. Using the product 96 instead of the lcm 24 would report only a quarter of the solutions.

An unsolvable system

Problem. Solve x ≡ 2 (mod 6) and x ≡ 4 (mod 9).

gcd(6, 9) = 3. Reduce both remainders modulo 3:

2 mod 3 = 2
4 mod 3 = 1        they disagree

No solution exists. The first congruence forces x to leave 2 on division by 3; the second forces it to leave 1. No integer can do both.

A Counting Application

Problem. A shipment of books is stacked in piles. In piles of 5 there are 3 books left over, in piles of 8 there is 1 left over, and in piles of 9 there are 7 left over. What is the smallest possible number of books?

Written as congruences:

x ≡ 3 (mod 5)
x ≡ 1 (mod 8)
x ≡ 7 (mod 9)

The moduli 5, 8 and 9 are pairwise coprime, so a unique answer exists modulo 5 × 8 × 9 = 360.

Merging the first two by substitution: x = 3 + 5t, and 3 + 5t ≡ 1 (mod 8) gives 5t ≡ 6 (mod 8). The inverse of 5 modulo 8 is 5, since 25 ≡ 1, so t ≡ 30 ≡ 6 (mod 8). Taking t = 6 gives x = 33, so x ≡ 33 (mod 40).

Merging that with the third: x = 33 + 40s, and 33 + 40s ≡ 7 (mod 9) gives 4s ≡ 1 (mod 9) after reducing 33 ≡ 6 and 40 ≡ 4. The inverse of 4 modulo 9 is 7, since 28 ≡ 1, so s ≡ 7 (mod 9). Taking s = 7:

x = 33 + 40 × 7 = 313

Answer. The smallest possible number is 313 books.

Verification. 313 = 5 × 62 + 3 ✓, 313 = 8 × 39 + 1 ✓, 313 = 9 × 34 + 7 ✓.

Where the Theorem Gets Used

• RSA decryption. Working modulo the two prime factors separately and recombining with the theorem is several times faster than working modulo their product.
• Secret sharing. Threshold schemes distribute residues against different moduli so that enough shares reconstruct the secret and too few reveal nothing.
• Calendar calculations. Cycles of different lengths, such as a 7 day week and a 28 day rota, line up at intervals governed by the theorem.
• Error detection. Residue number systems represent a large number by its remainders, which lets arithmetic run in parallel on small pieces.

Common Chinese Remainder Theorem Mistakes

• Skipping the coprimality check. Applying the construction formula to moduli that share a factor produces a number that fails at least one congruence.
• Checking the set instead of every pair. The moduli 2, 3 and 4 have no factor common to all three, yet 2 and 4 share one, so the classical theorem does not apply.
• Inverting the wrong number. The formula needs the inverse of Mᵢ modulo mᵢ, not the inverse of mᵢ.
• Using the product instead of the lcm in a non-coprime case, which overstates the modulus of the answer.
• Forgetting the final reduction. The sum in the construction method usually exceeds M and must be reduced.
• Reporting a single number as the answer. The solution is a congruence class. Writing x = 157 is incomplete; x ≡ 157 (mod 315) is the full answer.
• Not verifying. Every solution can be checked against every original congruence in a few seconds, so there is no reason to submit an unchecked answer.

Chinese Remainder Theorem Practice Problems

1. x ≡ 1 (mod 3), x ≡ 2 (mod 4)
2. x ≡ 2 (mod 5), x ≡ 1 (mod 6)
3. x ≡ 4 (mod 7), x ≡ 9 (mod 11)
4. x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 4 (mod 5)
5. x ≡ 3 (mod 4), x ≡ 4 (mod 5), x ≡ 5 (mod 7)
6. x ≡ 6 (mod 9), x ≡ 4 (mod 10)
7. x ≡ 2 (mod 4), x ≡ 8 (mod 10)
8. x ≡ 3 (mod 5), x ≡ 1 (mod 9), x ≡ 6 (mod 11)

Answers

1. M = 12. Testing 2, 6, 10 against mod 3 gives 10. x ≡ 10 (mod 12)
2. M = 30. x ≡ 7 (mod 30). Check: 7 = 5 + 2 ✓ and 7 = 6 + 1 ✓.
3. M = 77. Write x = 4 + 7t, so 4 + 7t ≡ 9 (mod 11) and 7t ≡ 5 (mod 11). The inverse of 7 is 8, so t ≡ 40 ≡ 7 (mod 11) and x = 4 + 49 = 53. x ≡ 53 (mod 77)
4. M = 30. x ≡ 29 (mod 30). Note that 29 ≡ −1 against all three moduli, which is a quick way to spot it.
5. M = 140. x ≡ 19 (mod 140). Check: 19 = 4 × 4 + 3 ✓, 19 = 5 × 3 + 4 ✓, 19 = 7 × 2 + 5 ✓.
6. gcd(9, 10) = 1, so the moduli are coprime and M = 90. x ≡ 24 (mod 90). Check: 24 = 9 × 2 + 6 ✓ and 24 = 10 × 2 + 4 ✓.
7. gcd(4, 10) = 2. Both remainders are even, so 2 mod 2 = 0 and 8 mod 2 = 0 agree and a solution exists modulo lcm(4, 10) = 20. x ≡ 18 (mod 20). Check: 18 = 4 × 4 + 2 ✓ and 18 = 10 × 1 + 8 ✓.
8. M = 495. Merging the first two gives x ≡ 28 (mod 45), and merging with the third keeps 28. x ≡ 28 (mod 495). Check: 28 = 5 × 5 + 3 ✓, 28 = 9 × 3 + 1 ✓, 28 = 11 × 2 + 6 ✓.

Chinese Remainder Theorem FAQ

What does the Chinese Remainder Theorem actually say?

That a set of congruences with pairwise coprime moduli always has a solution, and that the solution is unique modulo the product of the moduli. It converts a list of remainders back into the number that produced them.

Why must the moduli be coprime?

Because moduli that share a factor can impose contradictory demands. If x ≡ 2 (mod 6) and x ≡ 4 (mod 9), both statements say something about x modulo 3, and they disagree. Coprime moduli constrain independent aspects of the number, so they can never clash.

Can the theorem be used when the moduli share a factor?

Sometimes. The system is solvable exactly when every pair of remainders agrees modulo the gcd of their moduli, and the answer is then unique modulo the lcm rather than the product. The worked example above solves x ≡ 5 (mod 8) with x ≡ 9 (mod 12) this way.

How many solutions does a CRT system have?

Infinitely many integers, but exactly one residue class. With M = 315, the solutions are 157, 472, 787 and so on, plus −158 and downward. Writing the answer as x ≡ 157 (mod 315) captures all of them at once.

Do I need modular inverses to use the theorem?

For the construction formula, yes, one per congruence. Substitution also needs one per merge. The sieve needs none, which is why it is worth knowing for small systems. Methods for finding an inverse are covered in modular inverse.

What if one of the congruences has a modulus of 1?

Then it carries no information, since every integer is congruent to 0 modulo 1. Drop it and solve the rest.

Is this related to the polynomial Remainder Theorem?

No. They share the word “remainder” and nothing else. The polynomial Remainder Theorem is an algebra result about dividing f(x) by x − a. This one is a number theory result about reconstructing an integer from several remainders.

How do I check my answer quickly?

Divide the answer by each modulus in turn and compare the remainder to the one you were given. Every congruence must hold, not just the first. The Remainder Calculator does each division in one step.