Integer Combination of Coprime Integers/Proof 1

From ProofWiki
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