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