5x ≡ 3 (mod 7)
x ≡ 2
5·2 = 10 ≡ 3.
The congruence has a solution if and only if ; when it does, there are exactly solutions modulo .
This page is easier if you are comfortable with:
Example with gcd 1: . The inverse of 7 modulo 11 is 8 (since ), so ; check . The inverse comes from Bézout's identity (Bézout's identity) found with the Euclidean algorithm.
With gcd greater than 1: has , which divides 6, so there are 3 solutions modulo 9. Divide through by : , so . And : does not divide 3, so there is no solution (the left side is always even, the right side is odd mod 2).
Systems of congruences are solved together by the Chinese remainder theorem, powers by Fermat's little theorem and Euler's theorem (the inverse of is ), and the idea underlies RSA. The quadratic analogue is Euler's criterion.
A linear congruence is solved with a modular inverse, or has no solution when the gcd does not divide the right side.
Each residue occurs exactly once because gcd(7, 11) = 1.
These examples are worked by hand, step by step, so you can compare your own working.
Solve .
Solve .
Solve .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
x ≡ 2
5·2 = 10 ≡ 3.
3
5·3 = 15 ≡ 1.
gcd 2 divides 2: two solutions
x = 2 or 5.
gcd 3: three solutions
x = 2, 5, 8.
ax ≡ b (mod n) is solvable iff g = gcd(a, n) divides b, and then there are g solutions modulo n. For g = 1, x ≡ a⁻¹b.
Check x = 2 in 5x ≡ 3 (mod 7).
Check 5·3 mod 7.
Check x = 5 in 4x ≡ 2 (mod 6).
Check x = 8 in 3x ≡ 6 (mod 9).
x = b/a ✗
multiply by the inverse ✓
Modular arithmetic.
always one solution ✗
g solutions or none ✓
Count g.
g ∤ b ✗
check divisibility first ✓
2x ≡ 1 (mod 4) has none.
one residue ✗
all residues ≡ x mod n/g ✓
Spacing n/g.
Try each one on paper, then open the answer. Use the solver above to see the full working.
1
1
1
0
8
1
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
When gcd(a, n) divides b.
gcd(a, n) modulo n.
Multiply by the inverse of a.
Bézout or Euclid.
Fermat’s little theorem.
Chinese remainder theorem.
More in Discrete maths and number theory and the formula sheets.