Master the Chinese Remainder Theorem for SASMO Number Theory Problems
The Chinese Remainder Theorem (CRT) often feels like a magic trick. You have a number that leaves a remainder of 2 when divided by 3, and a remainder of 3 when divided by 5. Without any obvious starting point, CRT lets you find that number. For students preparing for the Singapore and Asian Schools Math Olympiad, mastering this theorem can be the difference between staring at a blank page and writing down a clean solution. It appears regularly in SASMO number theory problems, and once you understand the logic, it becomes one of the most reliable tools in your kit. Let’s walk through exactly how it works, how to apply it, and how to avoid the traps that trip up most competitors.
The Chinese Remainder Theorem lets you solve systems of modular equations when the moduli are coprime. For SASMO, the key is to break a large problem into smaller pieces, solve each piece, then combine them using a systematic method. Practice with small numbers first, then scale up to the harder competition problems.
Understanding the Core Idea
The Chinese Remainder Theorem deals with systems of simultaneous congruences. A congruence is just a fancy way of saying “this number leaves a specific remainder when divided by another number.” For example, x ≡ 2 (mod 3) means x leaves a remainder of 2 when divided by 3.
The theorem states that if you have a set of moduli that are pairwise coprime (no common factors between any two), there is exactly one solution modulo the product of all the moduli. In plain English, if you know the remainders of a number when divided by several different numbers that share no common factors, you can find the original number.
A Step-by-Step Method for SASMO Problems
Here is the practical process you can use for any CRT problem on the SASMO exam.
-
Write the system clearly. List each congruence: x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), and so on. Make sure the moduli are coprime. If they are not, the problem may still be solvable, but you need to check consistency.
-
Find the product M. Multiply all the moduli together. This number M will be the modulus of your final answer.
-
For each modulus, compute Mᵢ = M / mᵢ. This is the product of all moduli except the current one.
-
Find the modular inverse of Mᵢ modulo mᵢ. You need a number yᵢ such that Mᵢ * yᵢ ≡ 1 (mod mᵢ). This inverse exists because Mᵢ and mᵢ are coprime.
-
Combine the results. The solution is x = (a₁ * M₁ * y₁ + a₂ * M₂ * y₂ + …) mod M.
Let’s see this in action with a typical SASMO style problem.
Worked Example: A Classic SASMO Problem
Suppose you need to find the smallest positive integer that satisfies these conditions:
- When divided by 3, the remainder is 2.
- When divided by 5, the remainder is 3.
- When divided by 7, the remainder is 2.
Write the system:
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
Step 1: M = 3 * 5 * 7 = 105.
Step 2: Compute M₁, M₂, M₃.
M₁ = 105 / 3 = 35
M₂ = 105 / 5 = 21
M₃ = 105 / 7 = 15
Step 3: Find inverses.
We need y₁ such that 35 * y₁ ≡ 1 (mod 3). Since 35 mod 3 is 2, we need 2 * y₁ ≡ 1 (mod 3). That means y₁ = 2, because 2 * 2 = 4 ≡ 1 (mod 3).
We need y₂ such that 21 * y₂ ≡ 1 (mod 5). 21 mod 5 is 1, so 1 * y₂ ≡ 1 (mod 5). That gives y₂ = 1.
We need y₃ such that 15 * y₃ ≡ 1 (mod 7). 15 mod 7 is 1, so y₃ = 1.
Step 4: Combine.
x = (2 * 35 * 2) + (3 * 21 * 1) + (2 * 15 * 1)
x = 140 + 63 + 30 = 233
Step 5: Reduce modulo M.
233 mod 105 = 23. So the smallest positive solution is 23.
Check: 23 ÷ 3 = 7 remainder 2. 23 ÷ 5 = 4 remainder 3. 23 ÷ 7 = 3 remainder 2. It works.
Common Mistakes and How to Avoid Them
Even strong students make errors with CRT. Here are the most frequent ones, organized in a table for easy reference.
| Mistake | Why It Happens | How to Fix It |
|---|---|---|
| Forgetting to check that moduli are coprime | Students assume all systems are solvable | Always verify gcd(mᵢ, mⱼ) = 1 for every pair. If not, the system may have no solution or multiple solutions. |
| Getting the inverse wrong | Confusing the inverse of Mᵢ with the inverse of the remainder | Remember you need the inverse of Mᵢ modulo mᵢ, not the inverse of the remainder. |
| Adding instead of multiplying in the combination step | Rushing through the final formula | Write out each term carefully. The pattern is aᵢ times Mᵢ times yᵢ. |
| Forgetting to reduce modulo M at the end | Stopping at the large sum | Always take the final result mod M to get the smallest positive solution. |
When CRT Appears in SASMO
The Chinese Remainder Theorem SASMO questions usually fall into a few categories. You might see a direct system of two or three congruences. You might also encounter a problem where you need to set up the congruences yourself from a word problem. For example, a question might describe a number that leaves specific remainders when divided by different numbers, and you have to find that number.
Another common variation involves finding a number that satisfies a condition like “leaves remainder 1 when divided by 2, remainder 2 when divided by 3, and remainder 3 when divided by 4.” In this case, the moduli are not all coprime (2 and 4 share a factor), so you need to check consistency. This is a trick SASMO uses to test deeper understanding.
Expert advice: If the moduli are not coprime, rewrite the system. Sometimes you can combine congruences or eliminate redundant conditions. For example, x ≡ 3 (mod 4) already implies x ≡ 1 (mod 2), so you can drop the mod 2 condition if it matches.
Building Your Skills for Competition Day
Mastering CRT for SASMO takes practice, but you can build up gradually. Start with two congruences using small numbers. Work through ten problems until the process feels automatic. Then add a third modulus. Finally, try problems where you need to set up the congruences from a paragraph of text.
Here is a bulleted list of practice strategies that work well:
- Solve every problem twice. Once using the formula, and once by listing numbers until you find the match. This builds intuition.
- Create your own problems. Pick three small coprime numbers, choose remainders, and solve. Then check your answer.
- Time yourself. SASMO gives limited time per question. Aim to solve a two-modulus CRT problem in under two minutes.
- Use the answer to verify your method. If you get 23 in the example above, check it against all three conditions before moving on.
You can find more practice material in our Number Theory Practice Problems Every SASMO Competitor Should Master guide. For a broader view of how number theory fits into the competition, read Why Number Theory is the Secret Weapon Every SASMO Competitor Needs. And if you want to strengthen your foundation, our guide on 5 Essential Properties of Integers That Unlock Difficult SASMO Questions will help.
A Quick Reference for the Exam
When you are in the middle of the SASMO test, you do not have time to second guess the method. Keep this mental checklist handy.
- Are the moduli pairwise coprime? If yes, proceed. If no, check consistency.
- Write M as the product of all moduli.
- For each modulus, compute Mᵢ.
- Find yᵢ such that Mᵢ * yᵢ ≡ 1 (mod mᵢ).
- Sum the products aᵢ * Mᵢ * yᵢ.
- Reduce the sum modulo M.
That is the entire process. It takes about six lines of work on paper.
Your Turn to Practice
The best way to get comfortable with the Chinese Remainder Theorem SASMO style is to solve a problem right now. Try this one: Find the smallest positive integer that leaves a remainder of 1 when divided by 4, a remainder of 2 when divided by 5, and a remainder of 3 when divided by 9. Work through the steps we covered. When you finish, check your answer by plugging it back into each condition.
If you get stuck, review the method above. The solution is 157, but the real value comes from doing the work yourself. Once you solve it, you will have a new tool that will serve you well in every future SASMO competition. Keep practicing, and you will find that CRT problems become some of the easiest points on the paper.