Chinese Remainder Theorem Explained with Worked Examples

If are pairwise coprime, the system has a solution, unique modulo .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Chinese remainder theorem means

Sunzi's problem: , , . Here . Combine the first two: write ; then means , so and . Next write : means , so and . Check: , , . So .

Two more: , gives ; , gives . Each step solves a linear congruence (linear congruences) using inverses from Bézout's identity. The moduli must be coprime: if they share a factor the system may be inconsistent.

The theorem says that is isomorphic to the product of the , which is why (Euler's totient) and why cyclic groups of coprime orders combine (the fundamental theorem of finite abelian groups). It speeds up arithmetic in RSA (RSA) by working modulo and separately.

What is it used for?

The Chinese remainder theorem combines congruences with coprime moduli into one congruence modulo the product.

How to use chinese remainder theorem

  1. Check that the moduli are pairwise coprime.
  2. Write and substitute into the next congruence.
  3. Solve for , then combine moduli.
  4. Repeat and check each congruence.

Graph

The number 23 leaves remainders 2, 3 and 2 on division by 3, 5 and 723 mod 3 = 223 mod 5 = 323 mod 7 = 200.511.522.533.5401234567The number 23 leaves remainders 2, 3 and 2 on division by 3, 5 and 7modulus 3, 5, 7yGraph with x from 0 to 4 and y from 0 to 7.5. Shows bars (3); point 23 mod 3 = 2 at (1, 2); point 23 mod 5 = 3 at (2, 3); point 23 mod 7 = 2 at (3, 2).

The solution is unique modulo 105.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: Sunzi's problem

Solve , , .

Worked example
Answer
2323
  1. Combine mod 3 and 5
  2. Combine with mod 7

Example 2: moduli 4 and 9

Solve , .

Worked example Answer checked
Answer
29(mod36)29\pmod{36}
  1. Check

Example 3: moduli 5 and 7

Solve , .

Worked example Answer checked
Answer
18(mod35)18\pmod{35}
  1. Check

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

x ≡ 2 (3), x ≡ 3 (5)

x ≡ 8 (mod 15)

8 mod 3 = 2, 8 mod 5 = 3.

x ≡ 1 (4), x ≡ 2 (9)

x ≡ 29 (mod 36)

Check.

Three congruences

x ≡ 23 (mod 105)

2 (3), 3 (5), 2 (7).

Modulus

3 × 5 × 7

105.

Word problems

If the moduli m₁, …, m_k are pairwise coprime, the system x ≡ aᵢ (mod mᵢ) has a unique solution modulo M = ∏mᵢ.

Two moduli

Check x = 8 against x ≡ 2 (mod 3).

  1. 8 mod 3
  2. Check: 2 ✓2

Second condition

Check x = 8 against x ≡ 3 (mod 5).

  1. 8 mod 5
  2. Check: 3 ✓3

Different moduli Higher

Check x = 29 modulo 9 (needs 2).

  1. 29 mod 9
  2. Check: 2 ✓2

Three moduli Higher

Find the combined modulus for 3, 5, 7.

  1. 3 × 5 × 7
  2. Check: ✓105

Common mistakes

Non-coprime moduli

always solvable ✗

need pairwise coprime ✓

e.g. 4 and 6.

Modulus sum

3 + 5 ✗

3 × 5 ✓

Product.

Unique integer

one integer ✗

one residue class ✓

Add multiples of M.

Skipping verification

unchecked ✗

check each congruence ✓

Always check.

Exam tips

  1. Pairwise coprime moduli.
  2. M = ∏mᵢ.
  3. Check each congruence.
  4. Unique mod M.
  5. Inverses build the solution.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. 8 mod 5 Foundation

3

2. 23 mod 3 Foundation

2

3. 29 mod 4 Foundation

1

4. Modulus for 4, 9, 5 Higher

180

5. Smallest x with x≡1 (2), x≡2 (3) Higher

5

6. 23 mod 5 Higher

3

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Chinese remainder theorem
Solves simultaneous congruences.
Pairwise coprime
Every pair has gcd 1.
Combined modulus (M)
Product.
Residue class
All solutions mod M.
Modular inverse
Used in the construction.
Simultaneous congruence
System of congruences.

Frequently asked questions

What does the CRT say?

Coprime moduli give a unique solution modulo their product.

What is the combined modulus?

The product.

What if moduli are not coprime?

A solution may not exist.

How do I construct x?

Use modular inverses of M/mᵢ.

Which page covers linear congruences?

linear congruences.

Which page covers RSA?

RSA.

More in Discrete maths and number theory and the formula sheets.