The Chinese remainder theorem
Given pairwise coprime moduli n₁,…,n_k, the system x ≡ aᵢ (mod nᵢ) has a unique solution modulo the product N = n₁…n_k. Coprimality is essential: without it a system may have no solution at all. In practice the fastest hand method is successive substitution — solve two congruences, then feed the combined result into the next.
✓ Unlimited questions · marked criterion by criterion · no card needed
Method: how to approach it
The order below is what examiners expect to see, and each step carries its own marks.
- Check the moduli are pairwise coprimeIf not, the theorem does not apply directly; check consistency on the shared factors instead.
- Solve the first two by substitutionWrite x = a₁ + n₁t, substitute into the second congruence, and solve for t modulo n₂.
- Combine and repeatThe result is a single congruence modulo n₁n₂. Bring in the next modulus the same way.
- State the answer modulo the productThe solution set is a single residue class mod N — say so explicitly.
Worked example
Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7).
- From the first: x = 2 + 3t. Substitute into the second: 2 + 3t ≡ 3 (mod 5), so 3t ≡ 1 (mod 5).
- The inverse of 3 mod 5 is 2, so t ≡ 2 (mod 5), giving x = 2 + 3(2 + 5s) = 8 + 15s.
- Substitute into the third: 8 + 15s ≡ 2 (mod 7), so 1 + s ≡ 2, giving s ≡ 1 (mod 7).
- So x = 8 + 15(1 + 7u) = 23 + 105u.
Answer. x ≡ 23 (mod 105). Check: 23 = 3·7+2 ✓, 23 = 5·4+3 ✓, 23 = 7·3+2 ✓.
Where marks get dropped
These are the specific errors that cost credit on the chinese remainder theorem questions — QED's rubric penalises each of them separately.
- Applying the theorem with non-coprime moduli. x ≡ 1 (mod 2) and x ≡ 0 (mod 4) has no solution at all.
- Forgetting to state the modulus of the final answer. "x = 23" is incomplete; the solution set is 23 mod 105.
- Making an arithmetic slip and not checking. Substituting the answer back into all three congruences takes seconds.
Practise this until it is automatic
Unlimited fresh questions
QED generates new the chinese remainder theorem problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.
Marked like an examiner
Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.
Answer in real notation
A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.
Saved to your library
Every question you generate is kept and re-takeable as a timed exam, and your Number Theory mastery is tracked so you know when this is exam-ready.
The Chinese remainder theorem — frequently asked questions
Why must the moduli be coprime?
Because the map to the tuple of residues is a bijection only then. With a shared factor the congruences can contradict each other on that factor.
Is there a direct formula?
Yes: x = Σ aᵢ Nᵢ yᵢ mod N, where Nᵢ = N/nᵢ and yᵢ is the inverse of Nᵢ mod nᵢ. It is more work by hand than substitution but parallelises well.
Where is CRT used?
In RSA decryption (working mod p and q separately is about four times faster), and in splitting big-integer arithmetic across small moduli.
The rest of Number Theory
Divisibility, primes, gcd, modular arithmetic. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Divisibility & the division algorithm
- 2Primes & unique factorisation
- 3gcd, lcm & the Euclidean algorithm
- 4Modular arithmetic & congruences
- 5Solving linear congruences
- 6Fermat’s little theorem
- 7The Chinese remainder theorem
- 8Modular inverses & fast exponentiation
- 9Euler’s totient φ(n) & Euler’s theorem
- 10Base-b representations & digit arguments
- 11RSA & modular exponentiation in cryptography
- 12Wilson’s theorem & primality testing
- 13Linear Diophantine equations ax + by = c
Ready to make the chinese remainder theorem exam-proof?
Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.
Start practising free →