Linear Congruences

Definition

A linear congruence is a congruence of the form

ax\equiv b\pmod n,

where $a,b\in\mathbb{Z}$ , $n\in\mathbb{N}$ , and $x$ is the unknown integer.

This congruence means that

n\mid(ax-b).

Equivalently, there exists an integer $y$ such that

ax-b=ny.

Rearranging gives the linear Diophantine equation

ax-ny=b.

Thus solving a linear congruence is closely related to solving a linear equation in two integer variables.

First Examples

Consider

3x\equiv1\pmod7.

Testing residues modulo $7$ , we find

3\cdot5=15\equiv1\pmod7.

x\equiv5\pmod7

is the solution.

Now consider

4x\equiv2\pmod6.

Testing residues modulo $6$ ,

4\cdot2=8\equiv2\pmod6

and

4\cdot5=20\equiv2\pmod6.

Thus there are two residue classes of solutions:

x\equiv2\pmod6, \qquad x\equiv5\pmod6.

A linear congruence may therefore have no solution, one solution modulo $n$ , or several solutions modulo $n$ .

Solvability Criterion

The congruence

ax\equiv b\pmod n

has an integer solution if and only if

\gcd(a,n)\mid b.

Let

d=\gcd(a,n).

If $x$ is a solution, then

ax\equiv b\pmod n,

ax-b=ny

for some integer $y$ . Hence

b=ax-ny.

Since $d\mid a$ and $d\mid n$ , it follows that

d\mid b.

Conversely, if $d\mid b$ , Bezout’s identity gives integers $u,v$ such that

au+nv=d.

Multiplying by $b/d$ , we obtain

a\left(u\frac bd\right)+n\left(v\frac bd\right)=b.

Thus

a\left(u\frac bd\right)\equiv b\pmod n.

So the congruence has a solution.

The Coprime Case

The simplest case occurs when

\gcd(a,n)=1.

Then the congruence

ax\equiv b\pmod n

has a unique solution modulo $n$ .

Since $\gcd(a,n)=1$ , the integer $a$ has a multiplicative inverse modulo $n$ . Let this inverse be $a^{-1}$ . Multiplying both sides by $a^{-1}$ , we get

x\equiv a^{-1}b\pmod n.

For example, solve

5x\equiv3\pmod{11}.

Since

5\cdot9=45\equiv1\pmod{11},

the inverse of $5$ modulo $11$ is $9$ . Therefore

x\equiv9\cdot3=27\equiv5\pmod{11}.

So the solution is

x\equiv5\pmod{11}.

The General Case

Let

d=\gcd(a,n).

d\nmid b,

then

ax\equiv b\pmod n

has no solution.

d\mid b,

divide the congruence by $d$ . Write

a=da', \qquad b=db', \qquad n=dn'.

Then

da'x\equiv db'\pmod{dn'}.

This is equivalent to

a'x\equiv b'\pmod{n'}.

Now

\gcd(a',n')=1,

so the reduced congruence has a unique solution modulo $n'$ . This gives $d$ distinct solutions modulo $n$ .

Example of the General Case

Solve

6x\equiv9\pmod{15}.

We compute

d=\gcd(6,15)=3.

Since

3\mid9,

solutions exist.

Divide by $3$ :

2x\equiv3\pmod5.

The inverse of $2$ modulo $5$ is $3$ , because

2\cdot3=6\equiv1\pmod5.

Thus

x\equiv3\cdot3=9\equiv4\pmod5.

Modulo $15$ , this gives three solutions:

x\equiv4,9,14\pmod{15}.

Indeed,

6\cdot4=24\equiv9\pmod{15},

6\cdot9=54\equiv9\pmod{15},

and

6\cdot14=84\equiv9\pmod{15}.

Number of Solutions

For the congruence

ax\equiv b\pmod n,

let

d=\gcd(a,n).

If $d\nmid b$ , there are no solutions modulo $n$ .

If $d\mid b$ , there are exactly $d$ incongruent solutions modulo $n$ .

These solutions are separated by

\frac nd.

If $x_0$ is one solution to the reduced congruence modulo $n/d$ , then the full set of solutions modulo $n$ is

x\equiv x_0+k\frac nd\pmod n, \qquad k=0,1,\ldots,d-1.

Role in Number Theory

Linear congruences are the first equations of modular arithmetic. They connect divisibility, greatest common divisors, Bezout identities, and modular inverses.

They are used in solving Diophantine equations, constructing modular inverses, proving the Chinese remainder theorem, analyzing periodic sequences, and building cryptographic algorithms.

The key principle is simple: the congruence

ax\equiv b\pmod n

is solvable exactly when the common divisor structure of $a$ and $n$ is compatible with $b$ .