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
| \(\displaystyle a\) | \(\perp\) | \(\displaystyle b\) | |||||||||||
| \(\displaystyle \leadsto \ \ \) | \(\displaystyle \gcd \set {a, b}\) | \(=\) | \(\displaystyle 1\) | Definition of Coprime Integers | |||||||||
| \(\displaystyle \leadsto \ \ \) | \(\displaystyle \exists m, n \in \Z: m a + n b\) | \(=\) | \(\displaystyle 1\) | Bézout's Lemma |
Then we have:
| \(\displaystyle \exists m, n \in \Z: m a + n b\) | \(=\) | \(\displaystyle 1\) | |||||||||||
| \(\displaystyle \leadsto \ \ \) | \(\displaystyle \gcd \set {a, b}\) | \(\divides\) | \(\displaystyle 1\) | Set of Integer Combinations equals Set of Multiples of GCD | |||||||||
| \(\displaystyle \leadsto \ \ \) | \(\displaystyle \gcd \set {a, b}\) | \(=\) | \(\displaystyle 1\) | ||||||||||
| \(\displaystyle \leadsto \ \ \) | \(\displaystyle a\) | \(\perp\) | \(\displaystyle b\) | Definition of Coprime Integers |
$\blacksquare$
Sources
- 1958: Martin Davis: Computability and Unsolvability ... (previous) ... (next): Appendix $1$: Some Results from the Elementary Theory of Numbers: Theorem $7$
- 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$
