Integers Divided by GCD are Coprime

From ProofWiki
Jump to: navigation, search

Theorem

Any pair of integers, not both zero, can be reduced to a pair of coprime ones by dividing them by their GCD:

$\gcd \set {a, b} = d \iff \dfrac a d, \dfrac b d \in \Z \land \gcd \set {\dfrac a d, \dfrac b d} = 1$


That is:

$\dfrac a {\gcd \set {a, b} } \perp \dfrac b {\gcd \set {a, b} }$


Proof

Let $d = \gcd \set {a, b}$.

We have:

$d \divides a \iff \exists s \in \Z: a = d s$
$d \divides b \iff \exists t \in \Z: b = d t$

So:

\(\displaystyle \exists m, n \in \Z: d\) \(=\) \(\displaystyle m a + n b\) $\quad$ Bézout's Identity $\quad$
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle d\) \(=\) \(\displaystyle m d s + n d t\) $\quad$ Definition of $s$ and $t$ $\quad$
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle 1\) \(=\) \(\displaystyle m s + n t\) $\quad$ dividing through by $d$ $\quad$
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle \gcd \set {s, t}\) \(=\) \(\displaystyle 1\) $\quad$ Bézout's Identity $\quad$
\(\displaystyle \leadstoandfrom \ \ \) \(\displaystyle \gcd \set {\frac a d, \frac b d}\) \(=\) \(\displaystyle 1\) $\quad$ Definition of $s$ and $t$ $\quad$

$\blacksquare$


Also presented as

It can be expressed so as not to include fractions:

$\gcd \set {a, b} = d \iff \exists s, t \in \Z: a = d s \land b = d t \land \gcd \set {s, t} = 1$


Sources