# 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.
$$

So

$$
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,
$$

so

$$
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).
$$

If

$$
d\nmid b,
$$

then

$$
ax\equiv b\pmod n
$$

has no solution.

If

$$
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$.