Integer Combination of Coprime Integers/Proof 1

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$