Wednesday, 21 February 2018

elementary number theory - Does the Extended Euclidean Algorithm always return the smallest coefficients of Bézout's identity?

Bezout's identity says that there are integers x and y such that ax+by=gcd(a,b) and the Extended Euclidean Algorithm finds a particular solution. For instance,



33383+172816=gcd(333,1728)=9.



Will the Extended Euclidean Algorithm always return the smallest x and y that satisfy the identity? By small, I mean that |x|,|y| are minimized.



Because 333(83+1728t)+1728(16333t)=gcd(333,1728) is also a solution for all tZ.

No comments:

Post a Comment

real analysis - How to find limhrightarrow0fracsin(ha)h

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