HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Congruences and the Chinese Remainder Theorem
  1. 1Congruences and their rules
  2. 2Linear congruences and inverses
  3. 3The Chinese remainder theorem
  1. Mathematics
  2. /Congruences and the Chinese Remainder Theorem
  3. /The Chinese remainder theorem

Course 28.1·Lesson 3 of 3

The Chinese remainder theorem

When the moduli m1,m2,…,mkm_1, m_2, \dots, m_km1​,m2​,…,mk​

Lesson 3 of 3Show all lessonsHide
Congruences and the Chinese Remainder Theorem
  1. 1Congruences and their rules
  2. 2Linear congruences and inverses
  3. 3The Chinese remainder theorem

Try the code and the simulations beside the lesson.

What you will be able to do

  • solve a system of congruences with pairwise coprime moduli, in two ways;
  • decide when a system with a shared factor has a solution;
  • use the theorem to count solutions and to split a hard modulus into easy ones.

An old puzzle

A puzzle from a Chinese book of the third to fifth century, the Sunzi Suanjing, asks: there are some things whose number is unknown. Counted by threes, two are left. Counted by fives, three are left. Counted by sevens, two are left. How many things are there?

In our language: x≡2(mod3)x \equiv 2 \pmod 3x≡2(mod3), x≡3(mod5)x \equiv 3 \pmod 5x≡3(mod5), x≡2(mod7)x \equiv 2 \pmod 7x≡2(mod7). The answer is 232323, and every answer is 23+105k23 + 105k23+105k.

The theorem

The Chinese remainder theorem. Let m1,…,mkm_1, \dots, m_km1​,…,mk​ be positive integers, every two of which are coprime. Then for any integers a1,…,aka_1, \dots, a_ka1​,…,ak​ the system

x≡a1(modm1),…,x≡ak(modmk)\displaystyle x \equiv a_1 \pmod{m_1}, \quad \dots, \quad x \equiv a_k \pmod{m_k}x≡a1​(modm1​),…,x≡ak​(modmk​)

has a solution, and any two solutions differ by a multiple of M=m1m2⋯mkM = m_1 m_2 \cdots m_kM=m1​m2​⋯mk​.

Why one solution at most. If xxx and yyy both work, each mim_imi​ divides x−yx - yx−y. The mim_imi​ share no factor, so their product divides x−yx - yx−y.

Why one solution at least. Let Mi=M/miM_i = M / m_iMi​=M/mi​. It shares no factor with mim_imi​, so it has an inverse yiy_iyi​ modulo mim_imi​. Put

x=a1M1y1+a2M2y2+⋯+akMkyk.\displaystyle x = a_1 M_1 y_1 + a_2 M_2 y_2 + \dots + a_k M_k y_k.x=a1​M1​y1​+a2​M2​y2​+⋯+ak​Mk​yk​.

Modulo m1m_1m1​ every term but the first is 000, because m1m_1m1​ divides M2,…,MkM_2, \dots, M_kM2​,…,Mk​. The first term is a1⋅(M1y1)≡a1⋅1a_1 \cdot (M_1 y_1) \equiv a_1 \cdot 1a1​⋅(M1​y1​)≡a1​⋅1. The same works for each mim_imi​.

A grid of 15 cells with 3 rows and 5 columns. The rows are labelled by the remainder on division by 3 (0, 1, 2) and the columns by the remainder on division by 5 (0 to 4). Each number from 0 to 14 is written in the one cell that matches its two remainders, so every cell holds exactly one number. The cell in row 2 and column 3 holds 8, and it is circled.

Method 1: the formula

For the puzzle, M=105M = 105M=105, M1=35M_1 = 35M1​=35, M2=21M_2 = 21M2​=21, M3=15M_3 = 15M3​=15.

  1. Inverses. 35≡2(mod3)35 \equiv 2 \pmod 335≡2(mod3), inverse 222. 21≡1(mod5)21 \equiv 1 \pmod 521≡1(mod5), inverse 111. 15≡1(mod7)15 \equiv 1 \pmod 715≡1(mod7), inverse 111.
  2. Build. x=2×35×2+3×21×1+2×15×1=140+63+30=233x = 2 \times 35 \times 2 + 3 \times 21 \times 1 + 2 \times 15 \times 1 = 140 + 63 + 30 = 233x=2×35×2+3×21×1+2×15×1=140+63+30=233.
  3. Reduce. 233−2×105=23233 - 2 \times 105 = 23233−2×105=23.

Method 2: lifting, one congruence at a time

Most students find this faster by hand.

  1. From x≡2(mod7)x \equiv 2 \pmod 7x≡2(mod7), write x=2+7tx = 2 + 7tx=2+7t.
  2. Put it into the second: 2+7t≡3(mod5)2 + 7t \equiv 3 \pmod 52+7t≡3(mod5), so 2t≡12t \equiv 12t≡1, and t≡3(mod5)t \equiv 3 \pmod 5t≡3(mod5). Now t=3+5st = 3 + 5st=3+5s and x=23+35sx = 23 + 35sx=23+35s.
  3. Put it into the third: 23+35s≡2(mod3)23 + 35s \equiv 2 \pmod 323+35s≡2(mod3). Since 23≡223 \equiv 223≡2 and 35≡235 \equiv 235≡2, this is 2s≡02s \equiv 02s≡0, so s≡0(mod3)s \equiv 0 \pmod 3s≡0(mod3).

So x≡23(mod105)x \equiv 23 \pmod{105}x≡23(mod105).

Moduli that share a factor

Take x≡1(mod6)x \equiv 1 \pmod 6x≡1(mod6) and x≡3(mod4)x \equiv 3 \pmod 4x≡3(mod4). Both moduli contain 222. The first says xxx is odd, and the second says xxx is odd: they agree. Lifting gives x=1+6tx = 1 + 6tx=1+6t with 1+6t≡3(mod4)1 + 6t \equiv 3 \pmod 41+6t≡3(mod4), so 2t≡2(mod4)2t \equiv 2 \pmod 42t≡2(mod4), and ttt is odd. Then x≡7(mod12)x \equiv 7 \pmod{12}x≡7(mod12). The answer is unique modulo lcm⁡(6,4)=12\operatorname{lcm}(6, 4) = 12lcm(6,4)=12, not modulo 242424.

Now take x≡1(mod6)x \equiv 1 \pmod 6x≡1(mod6) and x≡2(mod4)x \equiv 2 \pmod 4x≡2(mod4). The first says odd, the second says even. There is no solution. In general, x≡a(modm)x \equiv a \pmod mx≡a(modm) and x≡b(modn)x \equiv b \pmod nx≡b(modn) can be solved exactly when gcd⁡(m,n)∣a−b\gcd(m, n) \mid a - bgcd(m,n)∣a−b.

Splitting a modulus

The theorem also works backwards. A remainder modulo M=m1m2M = m_1 m_2M=m1​m2​ is the same as a pair of remainders, one modulo m1m_1m1​ and one modulo m2m_2m2​. So a hard question modulo MMM splits into easy ones.

Counting. How many xxx from 000 to 141414 satisfy x2≡1(mod15)x^2 \equiv 1 \pmod{15}x2≡1(mod15)? Modulo 333 there are 222 choices (±1\pm 1±1), and modulo 555 there are 222 (±1\pm 1±1). Each pair of choices gives one xxx, so there are 2×2=42 \times 2 = 42×2=4: they are 1,4,11,141, 4, 11, 141,4,11,14.

A last-digits trick. To find a number modulo 100010001000, find it modulo 888 and modulo 125125125, then combine.

Practise with new numbers

Try it in Python

The program builds the solution of the old puzzle from the inverses, as in method 1, and compares it with a plain search.

Read it first. Then run it. Do the formula and the search agree?

1. Change the remainders to [1, 4, 6]. Predict the answer by lifting first.

2. Change the moduli to [4, 6, 7]. What goes wrong, and which line raises the error?

Common mistakes

  • Using the theorem with moduli that share a factor. First check that the remainders agree on the common part. The answer is then unique modulo the lcm.
  • Stopping at an answer bigger than MMM. Reduce it modulo MMM.
  • Forgetting that there are infinitely many solutions. The full answer is a whole residue class, like 23+105k23 + 105k23+105k.
  • Inverting the wrong number. In method 1 you invert MiM_iMi​ modulo mim_imi​, not mim_imi​ itself.

Remember these

  • Pairwise coprime moduli: exactly one solution modulo the product.
  • Lift: write x=a1+m1tx = a_1 + m_1 tx=a1​+m1​t and put it into the next congruence.
  • Shared factor: solvable exactly when gcd⁡(m,n)∣a−b\gcd(m, n) \mid a - bgcd(m,n)∣a−b, unique modulo the lcm.
  • A count modulo m1m2m_1 m_2m1​m2​ is the product of the counts modulo m1m_1m1​ and m2m_2m2​.

Check yourself

Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.

  1. Solve x≡1(mod4)x \equiv 1 \pmod 4x≡1(mod4) and x≡2(mod9)x \equiv 2 \pmod 9x≡2(mod9).
  1. Does the system x≡3(mod10)x \equiv 3 \pmod{10}x≡3(mod10), x≡8(mod15)x \equiv 8 \pmod{15}x≡8(mod15) have a solution?
  1. How many xxx from 000 to 343434 satisfy x2≡x(mod35)x^2 \equiv x \pmod{35}x2≡x(mod35)?
  1. A tray of sweets can be shared among 555 children with 444 left over, and among 666 children with 555 left over. Find the least possible number of sweets.
  1. In method 1 for the moduli 444, 555, 999, what is M2M_2M2​ and its inverse modulo 555?

References

  • David M. Burton, Elementary Number Theory, Chapter 4, section on the Chinese remainder theorem.

Enroll free in Congruences and the Chinese Remainder Theorem

Every lesson is open to read. Enrolling also lets you:

  • Mark lessons done and carry on where you stopped.
  • Take the tests of this lesson and its course.
  • Count the course towards the certificate for its chapter.
No payment. You can leave at any time.

Problems (3)

A farmer counts the eggs in a basket. Taken two, three, four, five or six at a time, one egg is…Hard · High School (11–12) · by StemPy Lab
The square of 376 is 141 376, which ends in 376 again…Advanced · High School (11–12) · by StemPy Lab
Two bells ring on their own schedules. A number x of minutes is wanted with x ≡ 5 pmod12 and x ≡ 11…Advanced · High School (11–12) · by StemPy Lab
That was the last lessonBack to the course: take the test
← Congruences and the Chinese Remainder Theorem
← Linear congruences and inversesNext →

Discussion (0)

Log in to join the discussion.

Loading…

share no factor in pairs, a system of congruences
x≡ai(modmi)x \equiv a_i \pmod{m_i}x≡ai​(modmi​)
has exactly one solution modulo their product. You can build it from inverses or find it by lifting one congruence at a time. With moduli that share a factor, the system is solvable only if the remainders agree on the common part.
about 25 min1 simulation1 practice question1 Python program5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

Python Labs (1)

A solver for the Chinese remainder theoremPython Lab · by StemPy Lab

Question Sets (1)

Congruences and the Chinese Remainder Theorem: Test Yourself10 questions · by StemPy Lab

Notes (1)

Congruences and the Chinese Remainder Theorem: Quick RevisionNote · by StemPy Lab