Congruence mod n
a ≡ b (mod n) means n divides a − b. This is the canonical equivalence relation: it has exactly n classes, one per remainder, and — crucially — it is compatible with addition and multiplication. That compatibility is what makes ℤ/nℤ a ring rather than just a set of classes, and it is the reason modular arithmetic works at all.
✓ 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 congruence to divisibilitya ≡ b (mod n) iff a − b = nk for some integer k. Every proof starts by writing this equation.
- Reduce to the canonical representativeReplace any integer by its remainder in {0, …, n−1}. This keeps numbers small and answers comparable.
- Use compatibility freelyIf a ≡ b and c ≡ d then a + c ≡ b + d and ac ≡ bd. Reduce at every step rather than at the end.
- Handle powers by reducing the base firstTo compute 7¹⁰⁰ mod 5, reduce 7 to 2 first, then look for a pattern or use Fermat.
Worked example
Compute 7¹⁰⁰ mod 5 using congruence arithmetic.
- 7 ≡ 2 (mod 5), so 7¹⁰⁰ ≡ 2¹⁰⁰ (mod 5).
- Powers of 2 mod 5 cycle: 2, 4, 3, 1, then repeat with period 4.
- 100 = 4 · 25, so 2¹⁰⁰ = (2⁴)²⁵ ≡ 1²⁵ (mod 5).
- Hence 2¹⁰⁰ ≡ 1 (mod 5).
Answer. 7¹⁰⁰ ≡ 1 (mod 5).
Where marks get dropped
These are the specific errors that cost credit on congruence mod n questions — QED's rubric penalises each of them separately.
- Cancelling a common factor without care. From 2a ≡ 2b (mod 6) you cannot conclude a ≡ b — cancellation needs gcd(factor, n) = 1.
- Reducing exponents mod n. Exponents reduce mod φ(n) when the base is coprime to n, not mod n itself.
- Giving a negative representative when the question asks for a value in {0,…,n−1}. −2 ≡ 3 (mod 5), and the canonical answer is 3.
Practise this until it is automatic
Unlimited fresh questions
QED generates new congruence mod n 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 Equivalence Relations mastery is tracked so you know when this is exam-ready.
Congruence mod n — frequently asked questions
Why is congruence compatible with arithmetic?
If a − b and c − d are both divisible by n, then (a + c) − (b + d) and ac − bd both factor to reveal a multiple of n. That two-line proof is what licenses all of modular arithmetic.
When can I divide in modular arithmetic?
Only by elements coprime to n, which are exactly the invertible ones. Modulo a prime every non-zero element is invertible, which is why prime moduli are so convenient.
How many classes does mod n have?
Exactly n, indexed by the possible remainders 0 through n − 1. The division algorithm guarantees each integer lands in exactly one.
The rest of Equivalence Relations
Equivalence classes, partitions and quotient sets. Each subtopic below has its own method, worked example and mark-losing traps.
- 1Verifying an equivalence relation
- 2Equivalence classes [a]
- 3The class–partition correspondence
- 4The quotient set A/∼
- 5Congruence mod n
- 6The kernel of a function as an equivalence
- 7Well-definedness of operations on classes
- 8Counting equivalence relations
- 9Equivalence closure of a relation
- 10Refinement of equivalence relations
- 11Intersections & unions of equivalence relations
- 12Bell numbers & counting partitions
- 13Isomorphism & similarity as equivalences
Ready to make congruence mod n 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 →