5
$\begingroup$

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?"

$\endgroup$
5
$\begingroup$

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)}|$$

$\endgroup$
0
3
$\begingroup$

The Extended Euclidean Algorithm finds the solution closest to the origin.

$\endgroup$
1
1
$\begingroup$

If there is one solution $(x,y)$ of the linear diophantine equation $ax+by=c$ then there are infinitely many, given by $(x-\dfrac b{\rm{gcd}(a,b)}t,y+\dfrac a{\rm{gcd}(a,b)}t)$ for any integer $t$.

There will be a solution at all if and only if $c$ is a multiple of the $\text{gcd}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.