Method for finding the coefficients in Bezout's identity without using extended euclidean algorithm

Question

Every book I have seen uses the extended euclidean algorithm for computing the coefficients of Bezout's identity. I feel that it is very tedious and time consuming. Is there a simpler and shorter method for finding the coefficients of Bezout's identity that always works? I have searched the internet but could not find any information regarding this anywhere.

Answer 1

Lets look at the identity:

$$xa-yb=\gcd(a,b)$$

It's obvious, that if $\gcd(a,b)=d$ that dividing out $d$, gives a solution for 1 in coprime parts. However we rarely have this. Also, over 60% of the time, $d=1$ source

We could reduce the greater of the pair mod the other. It won't guarantee a lot of savings, unless without loss of generality $a-b$ is small. In which case, there may not be many steps to begin with.

We could brute force $x,y$ using that they must be coprime, but that's even more tedious. Only makes a brute force knowing nothing ~66% faster.

Conclusion

There's not many extremely simple reductions you can apply except if you undrstand Bill's links.

Answer 2

Update: The OP's question and the other answer and the comments on this thread are thought provoking. I tried to 'jump over' the extended euclidean algorithm in some way, but found myself assuming, with $a \lt b$, that $b$ was not a prime.

In general, both the presented numbers $a$ and $b$ might be very large prime numbers, but you don't know anything about them. In that case you will no longer find the extended euclidean algorithm tedious - you'll have to respect it as an important result in mathematics.

---

Perhaps the OP doesn't like Euclidean division. In that case, they can calculate the coefficients using a simpler method, but it will take more steps.

Derive Bézout's identity for $a = 1239$ and $b = 735$ using only subtraction:

$1239 (1) + 735 (0) = 1239$
$1239 (0) + 735 (1) = 735$
$1239 (1) + 735 (-1) = 504$
$1239 (-1) + 735 (2) = 231$
$1239 (2) + 735 (-3) = 273$

$1239 (2) + 735 (-3) = 273$
$1239 (-1) + 735 (2) = 231$
$1239 (3) + 735 (-5) = 42$
$1239 (-4) + 735 (7) = 189$

$1239 (-4) + 735 (7) = 189$
$1239 (3) + 735 (-5) = 42$
$1239 (-7) + 735 (12) = 147$

$1239 (-7) + 735 (12) = 147$
$1239 (3) + 735 (-5) = 42$
$1239 (-10) + 735 (17) = 105$

$1239 (-10) + 735 (17) = 105$
$1239 (3) + 735 (-5) = 42$
$1239 (-13) + 735 (22) = 63$

$1239 (-13) + 735 (22) = 63$
$1239 (3) + 735 (-5) = 42$
$1239 (-16) + 735 (27) = 21$
$1239 (-19) + 735 (-32) = 21$

ANS: $1239 (-16) + 735 (27) = 21$