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≡3(mod5), x≡2(mod7). The answer is 23, and every answer is 23+105k.
The theorem
The Chinese remainder theorem. Let m1,…,mk be positive integers, every two of which are coprime. Then for any integers a1,…,ak the system
x≡a1(modm1),…,x≡ak(modmk)
has a solution, and any two solutions differ by a multiple of M=m1m2⋯mk.
Why one solution at most. If x and y both work, each mi divides x−y. The mi share no factor, so their product divides x−y.
Why one solution at least. Let Mi=M/mi. It shares no factor with mi, so it has an inverse yi modulo mi. Put
x=a1M1y1+a2M2y2+⋯+akMkyk.
Modulo m1 every term but the first is 0, because m1 divides M2,…,Mk. The first term is a1⋅(M1y1)≡a1⋅1. The same works for each mi.
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.
Put it into the second: 2+7t≡3(mod5), so 2t≡1, and t≡3(mod5). Now t=3+5s and x=23+35s.
Put it into the third: 23+35s≡2(mod3). Since 23≡2 and 35≡2, this is 2s≡0, so s≡0(mod3).
So x≡23(mod105).
Moduli that share a factor
Take x≡1(mod6) and x≡3(mod4). Both moduli contain 2. The first says x is odd, and the second says x is odd: they agree. Lifting gives x=1+6t with 1+6t≡3(mod4), so 2t≡2(mod4), and t is odd. Then x≡7(mod12). The answer is unique modulo lcm(6,4)=12, not modulo 24.
Now take x≡1(mod6) and x≡2(mod4). The first says odd, the second says even. There is no solution. In general, x≡a(modm) and x≡b(modn) can be solved exactly when gcd(m,n)∣a−b.
Splitting a modulus
The theorem also works backwards. A remainder modulo M=m1m2 is the same as a pair of remainders, one modulo m1 and one modulo m2. So a hard question modulo M splits into easy ones.
Counting. How many x from 0 to 14 satisfy x2≡1(mod15)? Modulo 3 there are 2 choices (±1), and modulo 5 there are 2 (±1). Each pair of choices gives one x, so there are 2×2=4: they are 1,4,11,14.
A last-digits trick. To find a number modulo 1000, find it modulo 8 and modulo 125, 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.
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 M. Reduce it modulo M.
Forgetting that there are infinitely many solutions. The full answer is a whole residue class, like 23+105k.
Inverting the wrong number. In method 1 you invert Mi modulo mi, not mi itself.
Remember these
Pairwise coprime moduli: exactly one solution modulo the product.
Lift: write x=a1+m1t and put it into the next congruence.
Shared factor: solvable exactly when gcd(m,n)∣a−b, unique modulo the lcm.
A count modulo m1m2 is the product of the counts modulo m1 and m2.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
Solve x≡1(mod4) and x≡2(mod9).
Does the system x≡3(mod10), x≡8(mod15) have a solution?
How many x from 0 to 34 satisfy x2≡x(mod35)?
A tray of sweets can be shared among 5 children with 4 left over, and among 6 children with 5 left over. Find the least possible number of sweets.
In method 1 for the moduli 4, 5, 9, what is M2 and its inverse modulo 5?
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.
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.