0
$\begingroup$

Obvious homework question, so hints please:

Suppose $a,b \in{\mathbb{Z}_+}$ and $c=\text{gcd}(a,b)$. So we know $\exists{x,y}\in{\mathbb{Z}}$ so that $a=cx$ and $b=cy$. Show that $\text{gcd}(x,y)=1$.

A hint was provided with the question, but I can't seem to get anywhere with it.

Begin by setting $d=\text{gcd}(x,y)$. How are $d$ and $x$ related? How are $d$ and $y$ related? What does this say about $a$ and $b$ in terms of $d$?

I realise I'm probably just missing something obvious, but I don't know what to do.

$\endgroup$
  • $\begingroup$ The hint is an overkill. Just give it a try $\endgroup$ – FormerMath Nov 17 '14 at 17:16
  • $\begingroup$ You need to start with how your book defines gcd. $\endgroup$ – vadim123 Nov 17 '14 at 17:16
2
$\begingroup$

$x=dx',y=dy'\implies a=(cd)x', b=(cd)y'$ and so $cd$ is a common divisor of $a$ and $b$.

This implies that $cd \mid c$ (or $cd \le c$), which can only happen if $d=1$.

$\endgroup$
0
$\begingroup$

Hint: You already have an answer but here goes an alternate proof. There's a theorem that $\gcd$ can be expressed as a linear combination. Using this you can prove

$\gcd(a,b)=c\iff \gcd(\frac{a}{c},\frac{b}{c})=1$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.