Linear Congruence Explained with Worked Examples

The congruence has a solution if and only if ; when it does, there are exactly solutions modulo .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Linear congruence means

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.

What is it used for?

A linear congruence is solved with a modular inverse, or has no solution when the gcd does not divide the right side.

How to use linear congruence

  1. Compute ; if there is no solution.
  2. Divide by .
  3. Find the inverse of modulo (Euclid).
  4. Solve and list the solutions modulo .

Graph

Values of 7x mod 11 for x = 0 to 10: the value 3 occurs at x = 2x = 2: 3x = 8 (inverse): 102468100246810Values of 7x mod 11 for x = 0 to 10: the value 3 occurs at x = 2x7x mod 11Graph with x from -1 to 11 and y from 0 to 11. Shows 7x mod 11 (11); point x = 2: 3 at (2, 3); point x = 8 (inverse): 1 at (8, 1).

Each residue occurs exactly once because gcd(7, 11) = 1.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: 7x ≡ 3 (mod 11)

Solve .

Worked example
Answer
x≡2(mod11)x\equiv2\pmod{11}
  1. Inverse of 7
  2. x

Example 2: 3x ≡ 6 (mod 9)

Solve .

Worked example
Answer
x≡2, 5, 8(mod9)x\equiv2,\ 5,\ 8\pmod9
  1. gcd
  2. Reduced

Example 3: 4x ≡ 3 (mod 6)

Solve .

Worked example
Answer
no solution\text{no solution}
  1. gcd

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

5x ≡ 3 (mod 7)

x ≡ 2

5·2 = 10 ≡ 3.

Inverse of 5 mod 7

3

5·3 = 15 ≡ 1.

4x ≡ 2 (mod 6)

gcd 2 divides 2: two solutions

x = 2 or 5.

3x ≡ 6 (mod 9)

gcd 3: three solutions

x = 2, 5, 8.

Word problems

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.

Invertible case

Check x = 2 in 5x ≡ 3 (mod 7).

  1. 10 mod 7
  2. Check: 3 ✓3

Inverse

Check 5·3 mod 7.

  1. 15 mod 7
  2. Check: 1 ✓1

gcd 2 Higher

Check x = 5 in 4x ≡ 2 (mod 6).

  1. 20 mod 6
  2. Check: ✓2

gcd 3 Higher

Check x = 8 in 3x ≡ 6 (mod 9).

  1. 24 mod 9
  2. Check: ✓6

Common mistakes

Dividing by a

x = b/a ✗

multiply by the inverse ✓

Modular arithmetic.

Ignoring gcd

always one solution ✗

g solutions or none ✓

Count g.

No solution mistaken

g ∤ b ✗

check divisibility first ✓

2x ≡ 1 (mod 4) has none.

Solutions mod n

one residue ✗

all residues ≡ x mod n/g ✓

Spacing n/g.

Exam tips

  1. gcd(a, n) | b.
  2. g solutions mod n.
  3. Inverse when g = 1.
  4. Test by substitution.
  5. Solutions spaced n/g apart.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. 3·5 mod 7 Foundation

1

2. 7·3 mod 10 Foundation

1

3. 2·4 mod 7 Foundation

1

4. 6·4 mod 8 Higher

0

5. 9·7 mod 11 Higher

8

6. 5·9 mod 11 Higher

1

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Linear congruence
ax ≡ b (mod n).
Modular inverse
a⁻¹ with aa⁻¹ ≡ 1.
gcd(a, n)
Decides solvability.
Residue
Value modulo n.
Solution count
g.
Reduced equation
Divide by g.

Frequently asked questions

When does ax ≡ b (mod n) have a solution?

When gcd(a, n) divides b.

How many solutions?

gcd(a, n) modulo n.

How do I solve when gcd = 1?

Multiply by the inverse of a.

How do I find the inverse?

Bézout or Euclid.

Which page covers Fermat’s little theorem?

Fermat’s little theorem.

Which page covers the Chinese remainder theorem?

Chinese remainder theorem.

More in Discrete maths and number theory and the formula sheets.