Solution of Linear Congruence/Existence

From ProofWiki
Jump to navigation Jump to search

Theorem

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


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


Proof

Consider the linear congruence $a x \equiv b \pmod n$.

Suppose $\exists x_0 \in \Z: a x_0 \equiv b \pmod n$.

Then $\exists y_0 \in Z: a x_0 - b = n y_0$ by definition of congruence.

Thus $x = x_0, y = y_0$ is a solution to the linear Diophantine equation $a x - n y = b$.


On the other hand, if $x = x_0, y = y_0$ is a solution to the linear Diophantine equation $a x - n y = b$, then it follows that $a x \equiv b \pmod n$.


Hence:

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


From Solution of Linear Diophantine Equation:

The linear Diophantine equation $a x - n y = b$ has at least one solution if and only if:

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


Hence the result.

$\blacksquare$