Tuesday, 27 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|<|\frac{b}{\gcd(a,b)}|
|y|<|\frac{a}{\gcd(a,b)}|


No comments:

Post a Comment

real analysis - How to find lim_{hrightarrow 0}frac{sin(ha)}{h}

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