Solution of Linear Congruence/Unique iff Coprime to Modulus

From ProofWiki
Jump to navigation Jump to search


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

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


Sufficient Condition

Necessary Condition

From Solution of Linear Congruence: Existence:

the problem of finding all integers satisfying the linear congruence $a x \equiv b \pmod n$

is the same problem as:

the problem of finding all the $x$ values in the linear Diophantine equation $a x - n y = b$.


$\gcd \set {a, n} = 1$

Let $x = x_0, y = y_0$ be one solution to the linear Diophantine equation:

$a x - n y = b$

From Solution of Linear Diophantine Equation, the general solution is:

$\forall k \in \Z: x = x_0 + n k, y = y_0 + a k$


$\forall k \in \Z: x_0 + n k \equiv x_0 \pmod n$

Hence $x \equiv x_0 \pmod n$ is the only solution of $a x \equiv b \pmod n$.