# $c=\text{gcd}(a,b)$ means $\exists{x,y}\in{\mathbb{Z}}$ so that $a=cx$ and $b=cy$. Show $\text{gcd}(x,y)=1$

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.

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

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