Integer Combination of Coprime Integers/Proof 1
Jump to navigation
Jump to search
Theorem
Two integers are coprime if and only if there exists an integer combination of them equal to $1$:
- $\forall a, b \in \Z: a \perp b \iff \exists m, n \in \Z: m a + n b = 1$
Proof
\(\ds a\) | \(\perp\) | \(\ds b\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \gcd \set {a, b}\) | \(=\) | \(\ds 1\) | Definition of Coprime Integers | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \exists m, n \in \Z: m a + n b\) | \(=\) | \(\ds 1\) | Bézout's Lemma |
Then we have:
\(\ds \exists m, n \in \Z: m a + n b\) | \(=\) | \(\ds 1\) | ||||||||||||
\(\ds \leadsto \ \ \) | \(\ds \gcd \set {a, b}\) | \(\divides\) | \(\ds 1\) | Set of Integer Combinations equals Set of Multiples of GCD | ||||||||||
\(\ds \leadsto \ \ \) | \(\ds \gcd \set {a, b}\) | \(=\) | \(\ds 1\) | |||||||||||
\(\ds \leadsto \ \ \) | \(\ds a\) | \(\perp\) | \(\ds b\) | Definition of Coprime Integers |
$\blacksquare$
Sources
- 1980: David M. Burton: Elementary Number Theory (revised ed.) ... (previous) ... (next): Chapter $2$: Divisibility Theory in the Integers: $2.2$ The Greatest Common Divisor: Theorem $2 \text{-} 4$
- 1982: Martin Davis: Computability and Unsolvability (2nd ed.) ... (previous) ... (next): Appendix $1$: Some Results from the Elementary Theory of Numbers: Theorem $7$