gcd property

**jozou** · July 22nd 2011, 01:19 AM

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.

**Trampeltier** · July 22nd 2011, 03:08 AM

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

**abhishekkgp** · July 22nd 2011, 03:58 AM

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

**jozou** · July 22nd 2011, 04:02 AM

Thank you Trampeltier, abhishekkgp. Finally I got it~

Thread: gcd property

LinkBack

Thread Tools

Display

gcd property

Re: gcd property

Re: gcd property

Re: gcd property

Similar Math Help Forum Discussions

[SOLVED] another gcd property

Mean Value Property Implies "Volume" Mean Value Property

set property help

One-To-One Property

property