# Math Help - gcd property

1. ## gcd property

Suppose $gcd(a, b) = 1$. Prove $gcd(c, b)$ divides $gcd(ac, b)$.

Attempt: Let $x = gcd(c, b)$, $y = gcd(ac, b)$. Then $\exists r_1, r_2$, s.t. $b = x . r_1$, $b = y . r_2$. Hence $y = x . r_1/r_2$.

I’m stuck after this, because I can’t show that $r_2$ divides $r_1$.

Can anyone help me? Thanks.

2. ## Re: gcd property

Hi,
try it this way:
d_1=gcd(c,b), d_2=gcd(ac,b)
=> cx_1+by_1=d_1 and acx_2+by_2=d_2
From gcd(a,b)=1 you get
=> ax+by=1 | *d_1
=> d_1=cx_1+by_1
Now we have to show, that d_2|d_1:

d_1*(ax+by=1) => ax(cx_1+by_1)+bd_1y=d_1 => ac(xx_1)+b(axy_1+d_1y)=d_1
You know d_2=gcd(ac,b), so d_2 divides any linear combination of ac and b => d_2|d_1

Repeat the steps for d_2 and you will get d_1|d_2 and d_2|d_1 => d_1=d_2

Greetings

3. ## Re: gcd property

Originally Posted by jozou
Suppose $gcd(a, b) = 1$. Prove $gcd(c, b)$ divides $gcd(ac, b)$.

Attempt: Let $x = gcd(c, b)$, $y = gcd(ac, b)$. Then $\exists r_1, r_2$, s.t. $b = x . r_1$, $b = y . r_2$. Hence $y = x . r_1/r_2$.

I’m stuck after this, because I can’t show that $r_2$ divides $r_1$.

Can anyone help me? Thanks.
hello jozou!
the condition $gcd(a,b)=1$ forces $gcd(c,b)=gcd(ac,b)$.

4. ## Re: gcd property

Thank you Trampeltier, abhishekkgp. Finally I got it~