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

Could someone please help me with this proof?

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?

Thanks in advance.

Solution 1:

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).

Solution 2:

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.