Course contentsShow
← Mathematics
Lesson 2737 of 3,12154. Number TheoryFree lesson

Solving Linear Congruences

Solve equations of the form ax ≡ b (mod n) using gcd conditions and modular inverses.

Solving Linear Congruences

You'll learn how to solve equations of the form ax ≡ b (mod n) by applying the gcd condition and modular inverses.

What Are Linear Congruences?

A linear congruence is an equation like ax ≡ b (mod n), where you're looking for all values of x that satisfy the relationship. Think of it as solving ax = b, but in the world of modular arithmetic—where numbers "wrap around" at n.

The Key Question: Does a Solution Exist?

Not every linear congruence has a solution. The solvability condition is:

A solution exists if and only if gcd(a, n) divides b.

If gcd(a, n) = d and d divides b, then there are exactly d solutions modulo n.

How to Solve

Case 1: gcd(a, n) = 1

When a and n are relatively prime, the congruence has a unique solution modulo n. Simply find the modular inverse of a (call it a⁻¹) and multiply both sides:

x ≡ a⁻¹b (mod n)

Example: Solve 7x ≡ 3 (mod 10)

Since gcd(7, 10) = 1, we find 7⁻¹ ≡ 3 (mod 10) using the extended Euclidean algorithm. Then x ≡ 3 · 3 ≡ 9 (mod 10).

Case 2: gcd(a, n) = d > 1

If d divides b, divide the entire congruence by d:

(a/d)x ≡ (b/d) (mod n/d)

Now gcd(a/d, n/d) = 1, so solve as in Case 1. The solution will give you one value, and you'll have d distinct solutions modulo n.

Example: Solve 6x ≡ 9 (mod 15)

gcd(6, 15) = 3, and 3 divides 9 ✓. Simplify: 2x ≡ 3 (mod 5). Find 2⁻¹ ≡ 3 (mod 5), so x ≡ 9 ≡ 4 (mod 5). The three solutions mod 15 are: 4, 9, 14.

Key Takeaway: Linear congruences ax ≡ b (mod n) are solvable when gcd(a, n) divides b; use modular inverses to find solutions.