Integer Coprime to Modulus iff Linear Congruence to 1 exists/Corollary

Theorem

Let $p$ be a prime number.

The linear congruence:

$a x \equiv 1 \pmod p$

has a solution $x$ if and only if $a \not \equiv 0 \pmod p$.

Proof

By definition of congruence:

$a \not \equiv 0 \pmod p \iff p \nmid a$

where $p \nmid a$ denotes that $p$ is not a divisor of $a$.

From Prime not Divisor implies Coprime:

$p \nmid a \iff p \perp a$

where $p \perp a$ denotes that $p$ and $a$ are coprime.

The result follows from Integer Coprime to Modulus iff Linear Congruence to 1 exists.

$\blacksquare$

Sources

• 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): $\S 2.3$: Congruences: Proposition $2$: Corollary