Modular arithmetic & congruences
a ≡ b (mod n) means n ∣ (a − b). Congruence is compatible with addition, subtraction and multiplication, so you may reduce at any stage — which is what keeps computations small. Division is the exception: cancelling a factor c is only valid when gcd(c,n) = 1, and forgetting that condition produces confidently wrong answers.
✓ 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.
- Convert to divisibility when provinga ≡ b (mod n) iff a − b = nk. Every proof starts here.
- Reduce early and oftenReplace each number by its remainder before multiplying. This is the whole practical benefit.
- Cancel only when coprimeca ≡ cb (mod n) gives a ≡ b (mod n/gcd(c,n)), not necessarily mod n.
- Use residue cases for proofsTo prove a statement for all integers, split into the n residue classes and check each.
Worked example
Show that n² ≡ 0 or 1 (mod 4) for every integer n, and deduce no integer of the form 4k+3 is a sum of two squares.
- Every n is even or odd. If n = 2m then n² = 4m² ≡ 0 (mod 4).
- If n = 2m+1 then n² = 4m² + 4m + 1 ≡ 1 (mod 4).
- So a sum of two squares is 0+0, 0+1, 1+0 or 1+1 mod 4.
- That gives 0, 1 or 2 mod 4 — never 3.
Answer. Squares are 0 or 1 mod 4, so a sum of two squares is never ≡ 3 (mod 4).
Where marks get dropped
These are the specific errors that cost credit on modular arithmetic & congruences questions — QED's rubric penalises each of them separately.
- Cancelling without checking coprimality. 6 ≡ 12 (mod 6) but cancelling 6 does not give 1 ≡ 2 (mod 6).
- Reducing exponents modulo n. Exponents reduce modulo φ(n) for coprime bases, not modulo n.
- Reporting a negative residue when a canonical one is wanted. −1 ≡ n−1 (mod n).
Practise this until it is automatic
Unlimited fresh questions
QED generates new modular arithmetic & congruences 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.
Modular arithmetic & congruences — frequently asked questions
When can I divide in modular arithmetic?
When the divisor is coprime to the modulus, so it has an inverse. Modulo a prime, every non-zero element qualifies.
Why is squares-mod-4 so useful?
Because it instantly rules out whole families of Diophantine equations. Checking a small modulus is the cheapest impossibility proof available.
What is ℤ/nℤ?
The ring of residue classes mod n. It is a field exactly when n is prime, which is why prime moduli behave so much better.
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 modular arithmetic & congruences 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 →