[Introduction to Number Theory Series Part 14] How Do We Solve Linear Congruences?

Now that we know what a modular inverse is, we can tackle one of the basic problems in modular arithmetic:

$$ax \equiv b \pmod n.$$

What this post covers

• What a linear congruence is
• The easy inverse case
• The general gcd-based existence condition
• Why some cases have more than one solution class

Key terms

• linear congruence: an equation of the form ax \equiv b \pmod n
• modular inverse: the multiplicative inverse modulo n
• congruence: the relation of equal remainders
• Chinese remainder theorem: a theorem for solving several congruences together

The easiest case: when an inverse exists

If gcd(a,n)=1, then a has an inverse modulo n. So we can multiply both sides by that inverse.

For example,

$$3x \equiv 4 \pmod 7.$$

Since the inverse of 3 modulo 7 is 5,

$$x \equiv 5\cdot 4 = 20 \equiv 6 \pmod 7.$$

In this case the solution is one congruence class modulo 7.

What if no inverse exists?

An inverse does not exist when gcd(a,n)>1. But that does not automatically mean there is no solution.

The true condition is:

ax \equiv b \pmod n has a solution if and only if gcd(a,n) divides b.

Let d=gcd(a,n). Then:

• if d \nmid b, there is no solution
• if d \mid b, there are solutions

Moreover, when d \mid b, the solutions typically split into d distinct congruence classes modulo n.

Example: a solvable non-inverse case

Consider

$$4x \equiv 2 \pmod 6.$$

Here

$$\gcd(4,6)=2,$$

and 2 divides 2, so solutions exist.

Testing values shows:

• x \equiv 2 \pmod 6
• x \equiv 5 \pmod 6

Both are solutions. So in this kind of case, more than one congruence class can appear. Here there are exactly two solution classes modulo 6, matching d=2.

Example: a no-solution case

Consider

$$4x \equiv 3 \pmod 6.$$

Again gcd(4,6)=2, but 2 does not divide 3, so no solution exists.

Why is this close to a Diophantine equation?

The congruence

$$ax \equiv b \pmod n$$

can be rewritten as

$$ax-b = ny,$$

or

$$ax+ny=b.$$

So linear congruences are closely tied to linear Diophantine equations.

Common mistakes

1. Thinking “no inverse” means “no solution”

The real condition is whether gcd(a,n) divides b.

2. Finding one solution and stopping

A congruence is usually about one or more full congruence classes, not a single isolated number.

3. Forgetting the modulus while manipulating the equation

A congruence must always be read with respect to the modulus.

Wrap-up

A linear congruence is solved by combining modular inverses with gcd conditions. The inverse case is the simplest, but the gcd condition is the full structural answer.

Next we solve several congruences at once with the Chinese remainder theorem.