# Integers Divided by GCD are Coprime

## Theorem

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

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

That is:

- $\dfrac a {\gcd \left\{{a, b}\right\}} \perp \dfrac b {\gcd \left\{{a, b}\right\}}$

Alternatively it can be expressed so as not to include fractions:

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

## Proof

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

We have:

- $d \mathrel \backslash a \iff \exists s \in \Z: a = d s$
- $d \mathrel \backslash 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 \iff \ \ \) | \(\displaystyle d\) | \(=\) | \(\displaystyle m d s + n d t\) | $\quad$ definition of $s$ and $t$ | $\quad$ | ||||||||

\(\displaystyle \iff \ \ \) | \(\displaystyle 1\) | \(=\) | \(\displaystyle m s + n t\) | $\quad$ dividing through by $d$ | $\quad$ | ||||||||

\(\displaystyle \iff \ \ \) | \(\displaystyle \gcd \left\{ {s, t}\right\}\) | \(=\) | \(\displaystyle 1\) | $\quad$ Bézout's Identity | $\quad$ | ||||||||

\(\displaystyle \iff \ \ \) | \(\displaystyle \gcd \left\{ {\frac a d, \frac b d}\right\}\) | \(=\) | \(\displaystyle 1\) | $\quad$ definition of $s$ and $t$ | $\quad$ |

$\blacksquare$

## Sources

- 1971: George E. Andrews:
*Number Theory*... (previous) ... (next): $\S 2.2$: Example $2.10$