Wednesday, 8 July 2015

algebra precalculus - Uniqueness of integers satisfying the Extended Euclidian algorithm

I would like to examine whether the following claim is true:



For the following equation:
ax+by=gcd(a,b)




where a,b,N and x,yZ, there exist x1,y1Z such that x1x,y1y and



ax1+by1=gcd(a,b)
I believe it holds and that it is also possible to express analytically x1,y1 in terms of x,y. I have reached the following point:
ax+by=gcd(a,b)ax+ax1ax1+by+by1by1=gcd(a,b)a(xx1)+b(yy1)+(ax1+by1)=gcd(a,b)a(xx1)+b(yy1)=0
where I used the fact that (ax1+by1)=gcd(a,b). After distinguishing cases I end up with $x>x_1, yy_1)and:x=(b/a)(yy1)+x1Butfromthatpointon,Icannotfigureouthowtocontinue,sincewhenItrytosubstitutefory=(\text{gcd}(a,b)-ax)/b,Iendupwithjusttherelationax_1+by_1=\text{gcd}(a,b)$.



There must be some wrong step in my proof but I cannot figure it out.

No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

How to find lim without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...