1
Solvability is a divisibility test
g = gcd(a,m) must divide b. That check is one gcd computation and it settles the question.
Lesson · Number Theory and Cryptography · Congruences
Linear Congruences
The modular analogue of a linear equation. It has either no solutions or exactly gcd(a,m) of them, and which case you are in is decided before any work is done.
ax ≡ b (mod m) solvable ⟺ g = gcd(a,m) divides b
then there are EXACTLY g solutions mod m
they are spaced m/g apart
if g = 1 the solution is x ≡ a⁻¹b, unique
Zero, one, or several
Core ideas
What this lesson establishes
Unlike a linear equation over the reals, this can have no solutions or many — and the gcd decides which.
2
The solution count is exactly g
Not one, and not m. The solutions form one class modulo m/g, which splits into g classes modulo m.
3
Coprime is the clean case
gcd(a,m) = 1 gives a unique solution x ≡ a⁻¹b, computed by the extended algorithm of “Bézout's Identity and Modular Inverses”.
The material
Solving ax ≡ b (mod m)
The criterion, the count, and the method.
Theorem · Solvability and count
Let g = gcd(a, m). The congruence ax ≡ b (mod m) has a solution if and only if g | b, and in that case it has exactly g solutions modulo m.
ax ≡ b (mod m) means ax − my = b for some integer y. By Bézout the set of values ax − my is exactly the multiples of g, so a solution exists precisely when g | b.
Suppose g | b and divide through: (a/g)x ≡ (b/g) (mod m/g). Now gcd(a/g, m/g) = 1, so this reduced congruence has a unique solution x₀ modulo m/g.
Lifting back, the solutions modulo m are x₀, x₀ + m/g, x₀ + 2m/g, …, x₀ + (g−1)m/g — exactly g of them.
□
Example · No solution
6x ≡ 7 (mod 15). gcd(6,15) = 3 and 3 ∤ 7, so there is no solution at all. Note that this is decided in one line, before any attempt to solve.
Example · Three solutions
6x ≡ 9 (mod 15). gcd(6,15) = 3 and 3 | 9, so three solutions exist. Divide through: 2x ≡ 3 (mod 5), and since 2⁻¹ ≡ 3 (mod 5), x ≡ 9 ≡ 4 (mod 5). Lifting: x ≡ 4, 9, 14 (mod 15). Check: 6·4 = 24 ≡ 9, 6·9 = 54 ≡ 9, 6·14 = 84 ≡ 9. All three work.
Example · One solution
7x ≡ 3 (mod 26). gcd(7,26) = 1, so exactly one solution. The inverse of 7 mod 26 is 15, since 7 · 15 = 105 = 4·26 + 1. So x ≡ 45 ≡ 19 (mod 26).
Why the count is the gcd
The reduced congruence lives modulo m/g and has one solution there. Each class modulo m/g contains exactly g classes modulo m, so one solution downstairs becomes g upstairs. Answering "one" or "m" both miss this, and the count matters for the systems of “The Chinese Remainder Theorem”.
Comparison with ordinary linear equations
over ℝ ax = b exactly one solution when a ≠ 0
mod m ax ≡ b (mod m) zero, or exactly gcd(a,m) solutions
The difference: ℝ is a field, so every nonzero a is invertible.
ℤ_m is a field only when m is prime.
That is the structural explanation. Over a field every nonzero coefficient can be divided out; modulo a composite m it cannot, and the failure is measured exactly by the gcd.
Interactive
Number theory workbench
Algorithms with their traces
Method
Solving a linear congruence
Compute the gcd first; it answers most of the question.
1
Compute g = gcd(a, m)
One run of Euclid. If g ∤ b, there is no solution and you are finished.
2
Divide the congruence through by g
All three of a, b and the modulus. The reduced coefficient is now coprime to the reduced modulus.
3
Invert and solve
x ≡ (a/g)⁻¹(b/g) (mod m/g), using the extended algorithm of “Bézout's Identity and Modular Inverses”.
4
Lift to the original modulus
Add multiples of m/g to produce all g solutions modulo m, and check at least one by substitution.
Linear congruences
Score 0 / 0Choose the answer you can justify.
14x ≡ 30 (mod 100)
A case with several solutions, worked in full.
g = gcd(14, 100) = 2, and 2 | 30, so TWO solutions exist.
Divide through by 2: 7x ≡ 15 (mod 50)
Invert 7 modulo 50: 7 · 43 = 301 = 6·50 + 1, so 7⁻¹ ≡ 43
x ≡ 43 · 15 = 645 ≡ 645 − 12·50 = 45 (mod 50)
Lift to modulus 100: x ≡ 45 and x ≡ 95
CHECK 14 · 45 = 630 = 6·100 + 30 ✓
14 · 95 = 1330 = 13·100 + 30 ✓
Both checks were worth doing: the lift is the step where a solution is most often lost. Reporting only x ≡ 45 would be half an answer, and reporting x ≡ 45 (mod 50) would be a correct statement about the wrong modulus.
Common mistakes
1
Reporting only one solution when there are gThe lift back to modulus m produces g classes. Stopping after the reduced congruence gives a correct statement about the wrong modulus.
2
Attempting to solve before checking the gcdOne gcd computation decides solvability. Without it you can search a long time for a solution that does not exist.
3
Dividing only the coefficient by gAll three of a, b and m must be divided. Leaving the modulus alone gives the wrong solution set.
Check your understanding
✓
Finish when the gcd is the first thing you compute.
Solve 15x ≡ 25 (mod 35), stating the number of solutions before finding any. gcd(15,35) = 5 divides 25, so there are five, spaced 7 apart.
Note: The same criterion governs the linear Diophantine equation ax + by = c, which is solvable in integers exactly when gcd(a,b) | c. The two statements are the same theorem written with and without congruence notation.