Suppose . Prove divides .

Attempt:Let , . Then , s.t. , . Hence .

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

Can anyone help me? Thanks.

Printable View

- Jul 22nd 2011, 01:19 AMjozougcd property
Suppose . Prove divides .

**Attempt:**Let , . Then , s.t. , . Hence .

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

Can anyone help me? Thanks. - Jul 22nd 2011, 03:08 AMTrampeltierRe: 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 - Jul 22nd 2011, 03:58 AMabhishekkgpRe: gcd property
- Jul 22nd 2011, 04:02 AMjozouRe: gcd property
Thank you Trampeltier, abhishekkgp. Finally I got it~