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

Question

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 — FormerMath, Nov 17 '14 at 17:16
You need to start with how your book defines gcd. – vadim123 Nov 17 '14 at 17:16 — vadim123, Nov 17 '14 at 17:16

score 2 · Accepted Answer · answered Nov 17 '14 at 17:16

2

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

answered Nov 17 '14 at 17:16

lhf

216,483

Swapnil Tripathi · Answer 2 · 2014-11-17T17:28:39.090

0

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$

edited Nov 17 '14 at 17:28

answered Nov 17 '14 at 17:18

Swapnil Tripathi

3,809

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

2 Answers2