Solving linear congruences
ax ≡ b (mod n) is solvable exactly when d = gcd(a,n) divides b, and then it has exactly d solutions modulo n. The method is to divide the whole congruence by d, invert the now-coprime coefficient, and then generate the d solutions by adding multiples of n/d. Stating the FULL solution set is what most exam schemes reward.
✓ 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.
- Compute d = gcd(a, n) and test divisibilityIf d ∤ b there are no solutions. Say so explicitly.
- Divide through by da/d · x ≡ b/d (mod n/d). The new coefficient is coprime to the new modulus.
- Invert and solveFind the inverse of a/d modulo n/d with the extended Euclidean algorithm and multiply.
- List all d solutions mod nTake the single solution x₀ mod n/d and add multiples of n/d: x₀, x₀ + n/d, …, up to d values.
Worked example
Solve 6x ≡ 9 (mod 15).
- d = gcd(6,15) = 3, and 3 ∣ 9 ✓, so there are 3 solutions mod 15.
- Divide by 3: 2x ≡ 3 (mod 5).
- The inverse of 2 mod 5 is 3, since 6 ≡ 1. So x ≡ 3·3 = 9 ≡ 4 (mod 5).
- Lift to mod 15 by adding multiples of 5: x = 4, 9, 14.
Answer. x ≡ 4, 9 or 14 (mod 15) — three solutions, as gcd(6,15) = 3 predicts.
Where marks get dropped
These are the specific errors that cost credit on solving linear congruences questions — QED's rubric penalises each of them separately.
- Giving only one solution when gcd(a,n) > 1. The number of solutions equals the gcd, and a single answer loses most of the marks.
- Dividing the modulus but not the other terms, or vice versa. All three of a, b and n divide by d.
- Trying to invert a when gcd(a,n) > 1. The inverse does not exist until you reduce the modulus.
Practise this until it is automatic
Unlimited fresh questions
QED generates new solving linear 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.
Solving linear congruences — frequently asked questions
How many solutions are there?
Exactly gcd(a,n) modulo n, provided that gcd divides b. Otherwise none.
What if gcd(a,n) = 1?
Then there is exactly one solution mod n: multiply both sides by the inverse of a. This is the easiest and most common case.
How do I find the inverse?
Extended Euclidean algorithm: solve ax + ny = 1 and take x mod n. For small moduli, trial multiplication is faster.
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 solving linear 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 →