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

\(\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