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