Engineering / Mathematics — Integer Foundations
Solving Linear Congruences
Solving ax = b (mod n): the solvability criterion, the exact number of solutions, and the algorithm via extended Euclid.
Executive summary
The linear congruence ax ≡ b (mod n) is the modular analogue of a linear equation, and unlike the real case it may have no solutions or many. The number is determined entirely by gcd(a, n).
The solvability criterion and the solution count are both consequences of Bezout's identity, and the algorithm is extended Euclid with a scaling step.
Learning objectives
- State the solvability criterion for a linear congruence.
- Determine the exact number of incongruent solutions.
- Execute the solution algorithm and handle the non-coprime case.
01When a solution exists
Solvability criterion
The congruence ax ≡ b (mod n) has a solution if and only if d = gcd(a, n) divides b.
When solvable, there are exactly d solutions modulo n, forming a single residue class modulo n/d.
The criterion follows from Bezout. The set of values ax mod n as x ranges over the integers is exactly the set of multiples of d in the range, because {ax + ny} is the ideal generated by d.
| Case | Condition | Solutions mod n |
|---|---|---|
| Unique | gcd(a, n) = 1 | Exactly one |
| Multiple | d = gcd(a, n) > 1 and d | b | Exactly d |
| None | d ∤ b | Zero |
02The algorithm
Solve ax ≡ b (mod n)
a, b, n with n > 0all x with ax ≡ b (mod n), or a report of insolubility- Compute d = gcd(a, n) together with Bezout coefficients s, t satisfying as + nt = d, using extended Euclid.
- If d does not divide b, report that no solution exists and stop.
- Set a' = a/d, b' = b/d, n' = n/d. Now gcd(a', n') = 1.
- The inverse of a' modulo n' is s mod n' (the same s from step 1).
- Compute x0 = b' · s mod n'.
- The full solution set modulo n is x0, x0 + n', x0 + 2n', ..., x0 + (d−1)n'.
O(len(n)²) bit operationsStep 4 deserves comment. The Bezout coefficient s from as + nt = d satisfies a's + n't = 1 after dividing through by d, so the same s serves as the inverse of a' modulo n' without a second Euclid run.
03Worked structure
Consider 6x ≡ 9 (mod 15). Here gcd(6, 15) = 3, which divides 9, so solutions exist and there are exactly three of them modulo 15.
Reduce
Divide through by 3: the congruence becomes 2x ≡ 3 (mod 5).
Invert
The inverse of 2 modulo 5 is 3, since 2·3 = 6 ≡ 1.
Solve reduced
x ≡ 3·3 = 9 ≡ 4 (mod 5).
Lift
The solutions modulo 15 are 4, 9 and 14.
04Frequently asked questions
Why exactly d solutions rather than some other count?
Because the reduced congruence has a unique solution modulo n/d, and each residue class modulo n/d splits into exactly d classes modulo n. The count is the index of the subgroup, not a coincidence of the arithmetic.
Is it necessary to run extended Euclid, or does plain Euclid suffice?
The extended version is needed. Plain Euclid returns the gcd, which settles solvability, but constructing the solution requires the Bezout coefficient, which only the extended version produces.
How does this generalise to systems of congruences?
Through the Chinese remainder theorem when the moduli are pairwise coprime. For non-coprime moduli a system is solvable exactly when every pair is consistent on the gcd of its moduli, and the combined solution is unique modulo the lcm.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 15-20.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.