# $d = \gcd(a,b)\Rightarrow\ \gcd(a/d,b/d) = 1$

Suppose that $a, b \in N$, and $d = \gcd(a, b)$. Since $d$ divides $a$, we have $a = de$ for some integer $e,$ and similarly $b = df$ for some integer $f$. Prove that $\gcd(e, f) = 1$.

I understand why it works. Since d is all the common factors of $a$ and $b, e$ and $f$ had no common factors, therefore the $\gcd(e,f) = 1$. But how do I prove this?

• Jul 5, 2020 at 13:43

It is special case of the gcd Distributive Law, namely

\begin{align} d &= \gcd(de,df)\\[.4em] \Longrightarrow\ \ d &= d\gcd(e,f)\ \ \ \text{by the gcd Distributive Law}\\[.4em] \smash{\overset{{\rm cancel}\ d}\Longrightarrow}\ \ 1 &=\gcd (e,f) \end{align}

The linked post has proofs of this law (by Bezout, universal property, and prime factorizations).

• this is the best answer, Mar 30, 2015 at 21:07

Suppose $\gcd(e,f)\neq 1$. Then $\exists p\in\mathbb P \left(\begin{cases}p\mid e\\p\mid f\end{cases}\right)$ and so $\begin{cases}dp\mid de=a\\dp\mid df=b\end{cases}$, contradiction.

• very helpful, thanks. Mar 30, 2015 at 20:59

You have the key idea of the proof. The challenge is now to make it rigorous.

Suppose that $e$ and $f$ have a common factor, $D$. We want to show that $D$ is already "included" in $d$.

From the two equations you wrote down, we have $Dd\mid a,b$. What does this tell you about $D$?

• it would say that d = Dd, which cannot be true. if d is really the gcd(a,b) Mar 30, 2015 at 20:58
• @DanielD'Souza or unless $D=1$ Mar 30, 2015 at 20:59