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.
try it this way:
=> 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
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