0
$\begingroup$

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.

$\endgroup$
1

3 Answers 3

2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ this is the best answer, $\endgroup$ Mar 30, 2015 at 21:07
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ very helpful, thanks. $\endgroup$ Mar 30, 2015 at 20:59
0
$\begingroup$

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$?

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .