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

## 3 Answers

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

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 The Extended Euclidean Algorithm finds the solution closest to the origin.