# Linear combination using extended GCD

Trying out different implementations of the extended GCD, i found out that all of them return the same linear combination factors for $$egcd(a,b)$$ and $$egcd(b,a)$$. For example (with this algorithm) I get:

$$egcd(257, 123) = [1,56,-117]$$ and $$egcd(123, 257) = [1,-117,56]$$

Which is correct, because:

$$egcd(257, 123) = 1 = 257 * (56) + 123 * (-117)$$ and $$egcd(123, 257) = 1 = 123 * (-117) + 257 * (56)$$

The two numbers are just switched, so their linear combination factors are switched as well.

So when I tried the binary version of the ecgd, i expected the same results. But using this algorithm (chapter 14.4.3) i now get two different linear combinations:

$$egcdBin(257, 123) = [1,56,-117]$$ and $$egcdBin(123, 257) = [1,140,-67]$$

Of course, both are correct again:

$$egcdBin(257, 123) = 1 = 257 * (56) + 123 * (-117)$$ and $$egcdBin(123, 257) = 1 = 123 * (140) + 257 * (-67)$$

For different $$(a,b)$$-pairs I found that sometimes the linear combination of $$egcd$$ and $$egcdBin$$ do not match (like above) and sometimes they do:

$$egcdBin(251, 123) = 1 = 251 * (-49) + 123 * (100)$$ and $$egcdBin(123, 251) = 1 = 123 * (100) + 251 * (-49)$$

which is the same as with the "normal" egcd.

So my question is: Why does the binary ecgd not give the same linear combination as the non-binary version?

Or better: Why does it sometimes produce the same combination and sometimes a different one?

(I know that there are infinite linear combinations possible, I'm just confused that with the binary version you sometimes get different ones.)