Category:Solution of Linear Congruence

This category contains pages concerning Solution of Linear Congruence:

Let $a x \equiv b \pmod n$ be a linear congruence.

The following results hold:

Existence

$a x \equiv b \pmod n$ has at least one solution if and only if:

$\gcd \set {a, n} \divides b$

that is, if and only if $\gcd \set {a, n}$ is a divisor of $b$.

Condition for Uniqueness

$a x \equiv b \pmod n$ has a unique solution if and only if $\gcd \set {a, n} = 1$.

Number of Solutions

Let $\gcd \set {a, n} = d$.

Then $a x \equiv b \pmod n$ has $d$ solutions which are given by the unique solution modulo $\dfrac n d$ of the congruence:

$\dfrac a d x \equiv \dfrac b d \paren {\bmod \dfrac n d}$