Integer Coprime to Modulus iff Linear Congruence to 1 exists

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $a, m \in \Z$.

The linear congruence:

$a x \equiv 1 \pmod m$

has a solution $x$ if and only if $a$ and $m$ are coprime.


Corollary

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

\(\ds a x\) \(\equiv\) \(\ds 1\) \(\ds \pmod m\)
\(\ds \leadstoandfrom \ \ \) \(\ds \exists y \in \Z: \, \) \(\ds a x + m y\) \(=\) \(\ds 1\) Definition of Congruence Modulo Integer


From Integer Combination of Coprime Integers:

$a \perp m \iff \exists x, y \in \Z: a x + m y = 1$


That is, such an $x$ exists if and only if $a$ and $m$ are coprime.

$\blacksquare$


Sources