Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 37 · Congruences

Solving Linear Congruences

Decide when ax = b (mod n) has solutions, count them, find all of them with the extended Euclidean algorithm and modular inverses, and solve systems in Python.

A linear congruence is an equation of the form

a·x ≡ b (mod n),

where you know a, b and n and want all integer x. It is the congruence version of the school equation ax = b. For example, 3x ≡ 4 (mod 7) asks: which multiples of 3 leave remainder 4 on division by 7? Trying x = 6 works, since 18 = 2 · 7 + 4.

The question has a complete answer: the equation is solvable exactly when gcd(a, n) divides b, and then the solutions are evenly spaced. You will prove it, use the extended Euclidean algorithm to compute solutions, and meet the special case of invertible a.

When gcd(a, n) = 1: use the inverse

If a and n are coprime, a has an inverse a⁻¹ modulo n, a number with a·a⁻¹ ≡ 1. Multiply both sides by it: x ≡ a⁻¹·b (mod n). There is exactly one solution class.

Python Solve with an inverse

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The general case

Let d = gcd(a, n).

Theorem. The congruence ax ≡ b (mod n) has a solution if and only if d | b. When it does, there are exactly d solutions modulo n, and they are x₀, x₀ + n/d, x₀ + 2n/d, ..., x₀ + (d − 1)n/d, where x₀ is any one solution.

Proof sketch. The congruence says ax − b = ny for some y, that is ax − ny = b. By Bezout, the values of ax − ny are exactly the multiples of d. So a solution exists exactly when d | b. If it does, divide everything by d: (a/d)x ≡ b/d (mod n/d). Now a/d and n/d are coprime, so this has a unique solution x₀ modulo n/d. Lifting to modulus n gives d solutions: x₀ + k·n/d for k = 0, ..., d − 1. ∎

The recipe is therefore:

  1. Compute d = gcd(a, n). If d ∤ b, report "no solution".
  2. Divide a, b, n by d.
  3. Compute the inverse of a/d modulo n/d and set x₀ = (b/d) · inverse mod (n/d).
  4. The solutions mod n are x₀ + k(n/d) for k = 0 ... d − 1.
Python A complete solver

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line tests 25,000 triples against brute force, so you can trust the solver.

Worked example

Solve 14x ≡ 30 (mod 100). Here d = gcd(14, 100) = 2, and 2 | 30, so there are 2 solutions modulo 100. Divide by 2: 7x ≡ 15 (mod 50). The inverse of 7 modulo 50 is 43 (since 7·43 = 301 = 6·50 + 1), so x ≡ 43·15 = 645 ≡ 45 (mod 50). The solutions modulo 100 are x = 45 and x = 95. Check: 14·45 = 630 ≡ 30 (mod 100), and 14·95 = 1330 ≡ 30.

Counting solutions

The number of solutions modulo n is 0 or gcd(a, n). Think of the map x → ax mod n: when gcd is d, the outputs are multiples of d only, and each reachable output is hit exactly d times.

Python Counting solutions by brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For n = 12 and a = 8 the output values are 0, 4, 8 only, each reached 4 times, because gcd(8, 12) = 4. That matches the theorem.

Systems of linear congruences, a first look

Sometimes you need x to satisfy two congruences at once: x ≡ 2 (mod 3) and x ≡ 3 (mod 5). Write x = 2 + 3k and substitute into the second: 2 + 3k ≡ 3 (mod 5), so 3k ≡ 1 (mod 5), k ≡ 2, x = 8. All solutions are x ≡ 8 (mod 15). The Chinese remainder theorem in chapter 4 makes this method systematic.

Python Substitution for two congruences

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Dividing both sides by a without checking gcd(a, n): you can lose or invent solutions.
  • Forgetting that there may be d solutions modulo n rather than one.
  • Computing a modular inverse when it does not exist: pow(6, -1, 9) raises ValueError.
  • Reporting the solution mod n/d as if it were mod n.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. How many solutions modulo 20 does 6x = 4 (mod 20) have?

    gcd(6, 20) = 2 divides 4, so there are 2 solutions modulo 20 (x = 4 and x = 14).
  2. 2. When is ax = b (mod n) solvable?

    ax - ny takes exactly the multiples of gcd(a, n) as values.
  3. 3. Solve 3x = 4 (mod 7).

    3 * 6 = 18 = 2 * 7 + 4. The inverse of 3 is 5 and 5 * 4 = 20 = 6 mod 7.
  4. 4. What is the inverse of 7 modulo 50?

    7 * 43 = 301 = 6 * 50 + 1.

Summary

  • ax ≡ b (mod n) is solvable exactly when d = gcd(a, n) divides b.
  • When solvable there are exactly d solutions mod n, spaced n/d apart.
  • If gcd(a, n) = 1 there is one solution, x ≡ a⁻¹b.
  • In general divide by d, invert a/d modulo n/d, then list the d lifts.
  • Substituting x = a₁ + m₁k solves pairs of congruences, which the Chinese remainder theorem will generalize.

Next: Residue Systems and Euler's Totient Function