Divide by GCD for Coprime Integers

Theorem

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

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

That is:

$\displaystyle \frac a {\gcd \left\{{a, b}\right\}} \perp \frac 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 \backslash a \iff \exists s \in \Z: a = d s$
• $d \backslash b \iff \exists t \in \Z: b = d t$

So:

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

$\blacksquare$

Sources

• George E. Andrews: Number Theory (1971): $\S 2.2$: Example $2.10$