JC1 H3 Mathematics Tutor Bukit Timah | Chinese Remainder Theorem and Simultaneous Congruences. Did you know? A number can leave remainder two when divided by three and remainder three when divided by five. The two clues are enough to identify one exact remainder class modulo fifteen, even though there are infinitely many integers that fit.
For JC1 Mathematics students in Bukit Timah, Sixth Avenue and Beauty World, the Chinese Remainder Theorem is an enriching application of modular arithmetic, proof and problem-solving. This guide starts with a simple search, develops a systematic method, and explains when multiple remainder conditions are compatible or impossible.
The official 2027 Singapore–Cambridge H3 Mathematics syllabus 9820 explicitly includes the concepts of congruence and modular arithmetic, as well as proof and non-routine reasoning. The Chinese Remainder Theorem is taught here as a distinctive number-theory enrichment topic, not claimed as a separately named compulsory subtopic. H2 Mathematics knowledge is assumed and each junior college determines H3 subject options.
The quick answer: when do simultaneous remainders work?
- A congruence x≡a (mod m) means m divides x−a. A remainder is an integer class, not a single integer.
- For coprime positive moduli m,n, the two conditions x≡a (mod m) and x≡b (mod n) always have a solution and determine one class modulo mn.
- For noncoprime moduli, a solution exists exactly when the two residues agree modulo gcd(m,n).
- When a solution exists for moduli m,n, the class is unique modulo lcm(m,n).
- Check proposed answers by dividing by every given modulus, and report the full class—not only one numerical example.
This theorem gives both existence and uniqueness of a residue class, not uniqueness of one integer. For example, a solution x≡8 (mod 15) represents …, −7, 8, 23, 38, 53 and every other integer of the form 8+15t. The least nonnegative solution is eight, but it is not the only integer solution.
Worked example: two remainders, one class
Find every integer x with x≡2 (mod 3) and x≡3 (mod 5). From the first condition write x=3k+2, where k is an integer. Substitute into the second: 3k+2≡3 (mod 5), so 3k≡1 (mod 5). Since the inverse of three modulo five is two, k≡2 (mod 5).
Thus k=2+5t and x=8+15t. Checking x=8: division by three leaves two and division by five leaves three. Every 15-unit shift preserves both remainders, and the coprimality of three and five shows the solution class modulo fifteen is unique.
The general construction using inverses
For coprime positive integers m,n, let N=mn. To solve x≡a (mod m), x≡b (mod n), choose u such that nu≡1 (mod m) and v such that mv≡1 (mod n). Then x=a n u+b m v (mod N).
Why? The term anu is congruent to a modulo m and zero modulo n. The term bmv is zero modulo m and congruent to b modulo n. Adding the terms satisfies both conditions. The inverse coefficients exist because the moduli are coprime, and any two solutions differ by a multiple of both moduli, hence by their product.
Original worked examples: construct, verify and interpret
Worked example 1: A four-and-seven system
Find x≡1 (mod 4) and x≡2 (mod 7). Write x=4k+1. The second condition gives 4k≡1 (mod 7). The inverse of four modulo seven is two because 4×2≡1, so k≡2 (mod 7).
The result is x=9+28t. Check nine: nine leaves one on division by four and two on division by seven. The answer is a residue class modulo 28, not just the integer nine. Both moduli are coprime, so the solution exists uniquely modulo their product.
Worked example 2: A five-and-seven system
Suppose x≡2 (mod 5) and x≡3 (mod 7). Begin with x=5k+2. Then 5k≡1 (mod 7). The inverse of five modulo seven is three, so k≡3 and x=17+35t.
The least nonnegative representative is 17. Verify it explicitly: 17=3×5+2 and 17=2×7+3. Naming both checks is a useful mathematical habit because one accidental remainder match is insufficient for a simultaneous system.
Worked example 3: Three pairwise coprime moduli
Find x≡2 (mod 3), x≡1 (mod 4), and x≡3 (mod 5). Combining the conditions modulo four and five yields x≡13 (mod 20), since 13 leaves remainders one and three. Write x=13+20k.
Modulo three, 13+20k≡1+2k must equal two, giving 2k≡1 and k≡2 (mod 3). Thus x≡53 (mod 60). Check 53 leaves two, one and three respectively. The moduli are pairwise coprime, so the class is unique modulo 60.
Worked example 4: A second three-modulus example
Find x≡1 (mod 3), x≡2 (mod 4), and x≡3 (mod 5). The number 18 has remainders two modulo four and three modulo five, so first write x=18+20k.
Modulo three, 18+20k≡2k must equal one, so k≡2 (mod 3). We obtain x≡58 (mod 60). Checking 58 gives remainders one, two and three. This second example changes only the given residues and reinforces that the combined modulus stays the product when the moduli remain pairwise coprime.
Worked example 5: A zero-remainder condition
Solve x≡0 (mod 4) and x≡1 (mod 5). The first condition gives x=4k, and the second gives 4k≡1 (mod 5), so k≡4 (mod 5). Therefore x≡16 (mod 20).
Check that 16 is a multiple of four and leaves one on division by five. Zero is a perfectly valid residue. A student should not mistake x≡0 for x=0, because the class includes every multiple of four subject to the other restriction.
Worked example 6: A direct CRT inverse construction
Return to x≡2 (mod 3), x≡3 (mod 5). Here N=15, N/3=5, whose inverse modulo three is two; and N/5=3, whose inverse modulo five is two.
The construction gives x≡2×5×2+3×3×2=38≡8 (mod 15). The result 38 differs from the least nonnegative representative eight by 30, a multiple of 15. A correct CRT formula can produce any representative, after which we reduce modulo the combined modulus.
Worked example 7: A system with an eight-and-nine modulus
Solve x≡7 (mod 8) and x≡1 (mod 9). From x=8k+7, reduce modulo nine to get −k+7≡1, so k≡6 (mod 9). Then x=55+72t.
Check 55 leaves seven modulo eight and one modulo nine. Because eight and nine are coprime, the solution class is unique modulo 72. Negative modular coefficients such as −k are legal and often simplify the calculation.
Worked example 8: A four-and-nine calculation
Find x≡1 (mod 4), x≡7 (mod 9). Write x=4k+1. Then 4k≡6 (mod 9). The inverse of four modulo nine is seven, so k≡42≡6 (mod 9).
Thus x≡25 (mod 36). The check is 25=6×4+1 and 25=2×9+7. A student can also discover 25 by listing a few candidates, but the inverse method explains why every answer has the form 25+36t.
Worked example 9: One remainder class in a finite range
Suppose x≡8 (mod 15) and the question asks for positive integers at most 100. Such integers are 8+15t with t≥0 and 8+15t≤100, so t≤92/15.
The permitted integer t values are 0 through six, giving seven solutions: 8,23,38,53,68,83,98. The Chinese Remainder Theorem gives the class; an inequality and integer count answer the separate bounded-range question.
Worked example 10: A least positive solution when the residue is zero
If a system yields x≡0 (mod 12), the least nonnegative solution is zero, but the least strictly positive solution is twelve. These are different requested quantities.
Writing x=12t with integer t makes the distinction clear. For a least positive integer, take t=1; for a least nonnegative one, take t=0. The words positive and nonnegative must not be treated as interchangeable.
Worked example 11: Negative representatives are still solutions
The integers −7 and 8 are congruent modulo 15, because their difference is 15. Both satisfy x≡2 (mod 3) and x≡3 (mod 5).
Thus there is no smallest integer solution over all integers: the class extends indefinitely in both directions. A minimum only exists when a lower bound, positivity or a restricted interval is part of the question.
Worked example 12: How uniqueness modulo the product works
Suppose x and y both satisfy x≡a (mod m), x≡b (mod n), and m,n are coprime. Then m divides x−y and n divides x−y.
Since the moduli are coprime, mn divides x−y. Therefore x≡y (mod mn). This proves uniqueness of the residue class rather than claiming that x and y are numerically equal.
Worked example 13: Noncoprime but compatible conditions
Solve x≡2 (mod 4) and x≡6 (mod 8). Every number congruent to six modulo eight leaves two modulo four. Thus the second condition already guarantees the first.
The full solution is x≡6 (mod 8). Because gcd(4,8)=4, the residues need only agree modulo four; indeed two and six differ by four. The class modulus is lcm(4,8)=8, not their product 32.
Worked example 14: Noncoprime with two independent conditions
Find x≡3 (mod 6) and x≡5 (mod 8). Their gcd is two, and both residues are odd, so compatibility is possible. Write x=6k+3. Modulo eight, 6k≡2.
Divide the congruence by gcd two, changing the modulus to four: 3k≡1 (mod 4), so k≡3 (mod 4). Then x=21+24t. Check 21 leaves three modulo six and five modulo eight, with period lcm(6,8)=24.
Worked example 15: Noncoprime and incompatible parity
Consider x≡1 (mod 4) together with x≡2 (mod 6). The first forces x to be odd, while the second forces x to be even. No integer can meet both.
Algebraically, gcd(4,6)=2, but the residues one and two are different modulo two. The compatibility theorem rules out every solution. Listing many candidates is unnecessary when a shared modulus gives a contradiction.
Worked example 16: A stronger consistency failure
Suppose x≡0 (mod 6) and x≡4 (mod 9). The gcd of six and nine is three. The first condition forces remainder zero modulo three, while the second gives remainder one modulo three.
The two conditions are incompatible, so no integer x exists. This proof works regardless of how far the search range is extended, which is the main advantage of a structural contradiction.
Worked example 17: A compatible six-and-nine system
Now change the second condition to x≡3 (mod 9), while retaining x≡0 (mod 6). Their residues agree modulo three. Write x=6k and require 6k≡3 (mod 9).
After dividing by three and changing the modulus, 2k≡1 (mod 3), so k≡2 (mod 3). Therefore x≡12 (mod 18). Verify 12 leaves zero modulo six and three modulo nine. A small change in residue changes impossibility to a unique lcm class.
Worked example 18: The general compatibility criterion
For positive moduli m,n and integer residues a,b, let g=gcd(m,n). A simultaneous solution exists if and only if g divides a−b. Necessity follows because g divides each of x−a and x−b, hence their difference a−b.
For sufficiency, write x=a+mk. The second condition becomes mk≡b−a (mod n). This linear congruence has an integer k exactly when gcd(m,n)=g divides b−a. When solvable, the resulting x is unique modulo lcm(m,n).
Worked example 19: A CRT puzzle with three digit remainders
Find the smallest nonnegative integer x satisfying x≡1 (mod 2), x≡2 (mod 3), and x≡3 (mod 5). First combine the conditions modulo two and three: x≡5 (mod 6).
Write x=5+6k. Modulo five, k≡3 because 5+6k≡k must equal three. The result is x≡23 (mod 30). Check: 23 is odd, leaves two on division by three and three on division by five.
Worked example 20: A timetable model with fixed cycles
Imagine two hypothetical displays whose status resets every four and seven minutes, measured from a common time zero. The first shows a specified state at minutes congruent to one modulo four; the second shows another state at minutes congruent to two modulo seven.
The first simultaneous occurrence is at minute nine, then every 28 minutes. This is an illustrative mathematical cycle model, not real public-transport schedule information. The assumptions of exact periodic resets and common starting time matter.
Worked example 21: A last-digit condition and a seventh remainder
Find x≡7 (mod 10), meaning its last decimal digit is seven, and x≡2 (mod 7). Write x=10k+7. Modulo seven, 3k≡2, so k≡3 (mod 7).
Thus x≡37 (mod 70), and 37 leaves remainder two on division by seven. This combines a decimal-digit requirement with a different modular restriction, a useful example of translating words into a congruence.
Worked example 22: An answer checked in two different ways
For x≡25 (mod 36), check the four-and-nine example. Any representative x=25+36t has x−1=24+36t divisible by four, and x−7=18+36t divisible by nine.
This algebraic check proves the whole class satisfies both conditions. Testing only the representative 25 would verify one solution but not directly show that every periodic shift is also valid.
Further CRT examples: compatibility, inverse coefficients and proof
Additional worked example 1: Three remainders just below each modulus
Find x≡2 (mod 3), x≡3 (mod 4) and x≡4 (mod 5). The number 59 has exactly those remainders, because it is one less than a multiple of three, four and five.
In fact the conditions say x≡−1 modulo each of 3,4,5. Their least common multiple is 60, so every solution satisfies x≡−1≡59 (mod 60). This is a short structural solution that avoids separate inverses.
Additional worked example 2: Solve a five-and-eight system
Find x≡4 (mod 5) and x≡3 (mod 8). Set x=5k+4. Modulo eight we need 5k≡7. The inverse of five modulo eight is five, since 25≡1, so k≡35≡3.
Therefore x≡19 (mod 40). Verify that 19 leaves four modulo five and three modulo eight. Writing k=3+8t demonstrates why the full integer solution is x=19+40t.
Additional worked example 3: Solve a seven-and-eleven system
Suppose x≡4 (mod 7) and x≡5 (mod 11). Write x=7k+4. Reducing modulo eleven gives 7k≡1. The inverse of seven modulo eleven is eight, since 56≡1.
Thus k≡8 and x≡60 (mod 77). Check 60=8×7+4 and 60=5×11+5. This is a useful larger example where an inverse avoids a long list of candidates.
Additional worked example 4: A nine-and-ten system
Find x≡4 (mod 9) and x≡7 (mod 10). Because the second condition fixes the final decimal digit, write x=10k+7. Modulo nine, k+7≡4, giving k≡6.
Hence x≡67 (mod 90). Checking both congruences is essential: 67 leaves four modulo nine and seven modulo ten. The result illustrates how a decimal condition can combine with a coprime modulus.
Additional worked example 5: Five-and-six remainders
The system x≡2 (mod 5), x≡4 (mod 6) has solution x≡22 (mod 30). One method writes x=5k+2, then 5k≡2 modulo six, so −k≡2 and k≡4.
Thus x=22+30t. A second method lists numbers 4,10,16,22 satisfying the second condition and notices which leaves remainder two modulo five. Both methods agree, but algebra proves the complete class.
Additional worked example 6: Two zero residues
Suppose x≡0 (mod 3) and x≡0 (mod 4). Then both three and four divide x. Since they are coprime, twelve divides x. Thus x≡0 (mod 12).
The least nonnegative answer is zero, while the least strictly positive answer is twelve. A student who reports only x=0 misses the infinitely many other integer solutions.
Additional worked example 7: Repeated remainder with noncoprime moduli
Take x≡5 (mod 6) and x≡5 (mod 8). Every number x=5+24t satisfies both because 24 is the least common multiple of six and eight.
The system is compatible because the residues agree modulo gcd(6,8)=2. The period is 24, not 48. Multiplying two moduli is the correct period only in the coprime case.
Additional worked example 8: A four-and-six compatible system
Find x≡0 (mod 4), x≡4 (mod 6). Because gcd(4,6)=2 divides the residue difference, a solution exists. Write x=4k and require 4k≡4 modulo six.
Divide by two and use modulus three: 2k≡2, so k≡1 modulo three. Thus x≡4 (mod 12). It is easy to verify every 12-unit shift preserves both conditions.
Additional worked example 9: Another four-and-six system
Consider x≡3 (mod 4) and x≡1 (mod 6). The residues are both odd, so the shared parity condition is satisfied. Set x=4k+3; modulo six we need 4k≡4.
Dividing by two yields 2k≡2 (mod 3), or k≡1. Hence x≡7 (mod 12). This contrasts with the inconsistent system having residues one modulo four and two modulo six.
Additional worked example 10: Eight and twelve share a factor
Solve x≡6 (mod 8) and x≡10 (mod 12). Their gcd is four and both residues are two modulo four, so the system is compatible. The number 22 is a solution.
All solutions are x≡22 (mod 24), since lcm(8,12)=24. The distinction between a modulus product 96 and a least common multiple 24 prevents an incorrect report of too many residue classes.
Additional worked example 11: A three-modulus compatibility example
Suppose x≡2 (mod 4), x≡6 (mod 8), and x≡1 (mod 3). The second congruence implies the first, so combine x=6+8t with the third.
Modulo three, 6+8t≡2t must equal one, giving t≡2. Thus x≡22 (mod 24). This example shows how a redundant condition can be recognised and removed before solving the remaining system.
Additional worked example 12: A hypothetical 14-day and five-day schedule
Imagine two invented repeating activities measured from a shared day zero. The first occurs on days congruent to two modulo fourteen, and the second on days congruent to three modulo five.
Write x=14k+2. Modulo five, 4k+2≡3, so 4k≡1 and k≡4. Thus the first simultaneous day is 58 and the pattern repeats every 70 days. These are hypothetical cycles, not actual school or transport schedules.
Additional worked example 13: Find an inverse within the CRT method
To solve 11k≡1 (mod 13), observe that 11×6=66=5×13+1. Therefore six is an inverse of eleven modulo thirteen.
Such a coefficient lets a simultaneous remainder problem be solved without checking thirteen possible k values. The inverse exists because gcd(11,13)=1. If the gcd were greater than one, an inverse of one might not exist.
Additional worked example 14: The role of Bézout’s identity
If gcd(m,n)=1, Bézout gives integers u,v satisfying mu+nv=1. Reducing this identity modulo m shows nv≡1, while reducing modulo n shows mu≡1.
Thus the inverse coefficients needed in CRT exist. This provides an explanation of the construction formula rather than assuming modular inverses appear mysteriously whenever needed.
Additional worked example 15: The noncoprime compatibility proof
Let g=gcd(m,n). If x≡a (mod m), then g divides x−a; if x≡b (mod n), then g divides x−b. Subtracting these quantities shows g divides a−b.
This proves necessity: any simultaneous solution must have residues compatible modulo g. For sufficiency, write x=a+mk and solve mk≡b−a modulo n, which is possible exactly when g divides b−a.
Additional worked example 16: Uniqueness after a compatible noncoprime system
Suppose x and y are both solutions to congruences modulo m and n. Then m and n both divide x−y, so their least common multiple divides x−y.
Therefore the solution set is one class modulo lcm(m,n). This is true for noncoprime moduli as well as coprime ones whenever the system is compatible. The proof of uniqueness is distinct from the proof that a solution exists.
Additional worked example 17: A minimum under a bounded interval
If x≡22 (mod 30) and 100≤x≤200, write x=22+30t. The lower bound gives t≥78/30, hence t≥3, and the upper bound gives t≤178/30, hence t≤5.
The permitted integer values t=3,4,5 produce x=112,142,172. This is how a residue-class answer becomes an exact list inside a requested numerical range.
Additional worked example 18: A positive solution with a negative representative
The class x≡−7 (mod 15) can be written as x=−7+15t. For the least strictly positive solution, choose t=1 to get eight.
The negative representative is mathematically valid; it is not an error. The task’s positivity restriction determines which member of the class should be reported.
Additional worked example 19: CRT does not make incompatible remainders compatible
Suppose x≡0 (mod 4) and x≡1 (mod 2). The first forces evenness while the second requires oddness. There is no solution.
A student who automatically multiplies the moduli and writes x modulo eight has skipped the compatibility check. Existence under CRT’s simple product rule requires coprime moduli; here gcd(4,2)=2 and the residues disagree modulo two.
Additional worked example 20: The number of solutions modulo the product
For coprime m,n, one CRT class modulo mn contains exactly one representative among integers 0,1,…,mn−1. For m=3,n=5 and residues two and three, that representative is eight.
There are infinitely many integer solutions, but only one residue representative in that complete 15-integer range. Distinguishing integer solutions from residue classes prevents the misleading claim that CRT gives exactly one integer.
Additional worked example 21: A different interpretation of the same result
Suppose a nonnegative integer x has remainder two modulo three and remainder three modulo five. The possible x are 8,23,38,53,…, increasing by fifteen.
If a word problem asks for the 10th nonnegative solution, start with 8 as the first: the 10th is 8+9×15=143. Counting positions in an arithmetic sequence is an extra step after solving the congruences.
Additional worked example 22: Why a calculator search is not proof
A calculator can scan the first hundred integers for a matching remainder pair, but it cannot alone establish that all larger or negative solutions follow the same period. The congruence proof identifies the period and rules out other classes.
Technology is useful as a check after the algebra. Under a proof-based H3 question, the justification for existence, compatibility and uniqueness is the central mathematical work.
How a tutor should teach this without encouraging blind searching
A productive lesson begins with a simple pair of coprime moduli where listing a few possible numbers is manageable. Ask the learner to find a first solution and notice the recurring period. Next replace the search with x=a+mk and a modular inverse, verifying that this method produces the same class and explains every future solution.
Then change only one modulus so the moduli share a common factor. Ask whether the given residues agree modulo that gcd. Provide one compatible pair and one impossible pair. The purpose is to make the learner check the theorem’s hypotheses rather than automatically multiply moduli.
In a later independent exercise, ask for all solutions in a bounded interval and the least positive solution. These are different questions from “find one residue class”. A strong learner expresses the class first, then applies the range or positivity condition precisely.
Independent practice with an answer key
- A: Solve x≡4 (mod 5), x≡3 (mod 8).
- B: Solve x≡3 (mod 6), x≡5 (mod 8).
- C: Explain why x≡1 (mod 4), x≡2 (mod 6) has no solution.
- D: Solve x≡2 (mod 3), x≡1 (mod 4), x≡3 (mod 5).
- E: Count positive x≤100 with x≡8 (mod 15).
- F: State the correct solution period for noncoprime moduli when the system is compatible.
The answers are A: x≡19 (mod 40); B: x≡21 (mod 24); C: the residues have different parity despite gcd(4,6)=2; D: x≡53 (mod 60); E: seven values; F: lcm of the moduli. Check each answer against all original congruences, rather than only the final modulus.
Frequently asked questions
Is the Chinese Remainder Theorem separately listed in the 2027 H3 syllabus?
The 2027 H3 Mathematics syllabus 9820 includes congruence and modular arithmetic, as well as mathematical proof. This is an enrichment application; the theorem is not claimed here as an individually named compulsory subtopic.
Can the method be used when moduli share factors?
Yes, but compatibility must be checked: the residues must agree modulo the gcd of the moduli. If compatible, the period is their least common multiple, not automatically their product.
Does the theorem identify exactly one integer?
No. It identifies one residue class, which contains infinitely many integers. Additional constraints such as a range or least positive value choose particular representatives.
Should JC1 students master H2 Maths before using this method?
Yes. This number-theory problem solving should complement the student’s existing H2 algebra, functions and schoolwork; any H3 subject selection remains controlled by their junior college.
Official syllabus and related Bukit Timah Mathematics guides
Use the SEAB 2027 A-Level syllabus directory, modular arithmetic and congruences, and Euclidean algorithm and Bézout identity for the prerequisite and inverse construction.
The unchanged eduKateSG small-group Mathematics reference describes the established three-student approach near Sixth Avenue MRT; it does not establish a current JC1 H3 class or specialist availability. Enquire directly about appropriate JC Mathematics tutor expertise, available groups, schedules and fees.
Did you know? The Chinese Remainder Theorem is about much more than finding a clever number. It shows exactly when several modular clues can coexist—and why the combined answer repeats with a particular period.