Integer Coprime to Modulus iff Linear Congruence to 1 exists
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
- 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): $\S 2.3$: Congruences: Proposition $2$