Friday, 23 October 2015

elementary number theory - Uniqueness of Extended Euclidean Algorithm



I'm doing a bit of extra reading on the Extended Euclidean Algorithm and had a side-thought that I couldn't find an answer to in the book.



I understand that the Extended Euclidean Algorithm can express the GCD of two numbers as a linear combination of those two numbers.



My question is, is the linear combination acquired unique? (My gut is telling me that it not, but I'd like some verification as I cannot produce a proof of uniqueness).




If the answer is 'No', then my follow-up question is "What is so special about the specific linear combination acquired by the EEC?"


Answer



Given two integers a and b, the Extended Euclidean algorithm calculates the gcd and the coefficients x and y of Bézout's identity: ax+by=gcd(a,b). These coefficients are not unique (see linked article).



The specific coefficients created by the algorithm satisfy these conditions: |x|<|bgcd(a,b)|


|y|<|agcd(a,b)|


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