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,
333⋅−83+1728⋅16=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⋅(16−333t)=gcd(333,1728) is also a solution for all t∈Z.
No comments:
Post a Comment