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$
4
$\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$
3
$\begingroup$

In fact, the pair of $(x,y)$ obtained using extended Euclidean algorithm, is the "smallest" pair possible, which means for all other pairs $(x_1,y_1)$, $|x|<|x_1|$ and $|y|<|y_1|$

Lemma: Such "smallest" pair must exist.

Proof:

With $ax+by=(a,b)$ and $ax_1+by_1=(a,b)$, WLOG we first assume the sign of $x,x_1$ are the positive, $x\le x_1$ Then $y_1,y_2$ must be both negative.

$\implies a(x_1-x)=b(y-y_1)$

Left side is positive, so $(y-y_1)$ is also positive, $\implies y\ge y_1 \longrightarrow -y\le -y_1\longrightarrow |y|\le |y_1|$.

For if signs of $x_1,x_2$ are different, $|x|\le |x_1|$,

$\implies a(x_1+x)=b(y+y_1)$ ....(1)

For any pair $(x,y)$, $x,y$ must be of opposite signs.

(1) will prove that $|y|\le |y_1|$ no matter $x$ is positive or negative.


Finally, given $|x|<|\frac{b}{\gcd(a,b)}|$, $|y|<|\frac{a}{\gcd(a,b)}|$.

By adding the equation $a(\frac{b}{\gcd(a,b)})-b(\frac{a}{\gcd(a,b)})=0$ or $b(\frac{a}{\gcd(a,b)})-a(\frac{b}{\gcd(a,b)})=0$,

it can (actually cannot) be concluded that $|x|<|\frac{b}{2\gcd(a,b)}|$ and $|y|<|\frac{a}{2\gcd(a,b)}|$ as upper bounds.

Geometric meaning of this is as follows enter image description here

$\endgroup$
2
$\begingroup$

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

$\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.