2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Why wouldn't you use it. It is a fast algorithm, $O(L^3)$ steps where $L$ is the bit length of the modulus $n$. $\endgroup$ – Wuestenfux Jul 12 at 12:45
  • $\begingroup$ It's very tedious. I am looking for a simpler and less tedious method. $\endgroup$ – MrAP Jul 12 at 12:48
  • 1
    $\begingroup$ The Euclidean algorithm seems to be optimal ($\log(n)$ steps). IMO, this is anything but "tedious". And is one of the simplest algorithms of all times. $\endgroup$ – Yves Daoust Jul 12 at 13:06
  • 1
    $\begingroup$ Generally you won't find anything much faster than the extended Euclidean algorithm. But there are various optimizations that are convenient. Also we can eliminate one coefficient and do it in fractional form. $\endgroup$ – Bill Dubuque Jul 12 at 14:10
  • 3
    $\begingroup$ "Tedious" is not a mathematical judgement. You're asking us to guess your aesthetic, and that's not an appropriate question for MSE. $\endgroup$ – John Hughes Jul 12 at 23:40
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
  • 1
    $\begingroup$ That's essentially this version of the Extended Euclidean Algorithm, except computing remainders using repeated subtraction vs. division. That's even more "tedious and time consuming" than other approaches, so it's not clear why the OP would seek that. $\endgroup$ – Bill Dubuque Jul 13 at 20:01
  • $\begingroup$ @BillDubuque If you find subtraction exhilarating then this answer is for you (see John Hughes' comment).! Also, it doesn't feel like Gaussian elimination at all. You're only looking at one number, the one on the rhs of the equations. The $x, y$ coefficients come for the ride. $\endgroup$ – CopyPasteIt Jul 13 at 23:28
  • 1
    $\begingroup$ I'm not sure what you mean, but it really is exactly as I claim above. But you might need to be more familiar with the linked algorithm to see that clearly. $\endgroup$ – Bill Dubuque Jul 13 at 23:30
  • $\begingroup$ @BillDubuque The 'starter-kit' theory I used can be found here: math.stackexchange.com/a/718841/432081 I was looking at $(\Bbb Z,+)$ as a $\Bbb Z \text{-module}$, so yes, using equation form and subtraction I'm doing exactly what you detailed in your link. The logic here was to find the subgroup generated by $a$ and $b$ in a "Bezout's Identity for Dummies" method (just need a pinch of group theory and a dash of set theory). $\endgroup$ – CopyPasteIt Jul 14 at 14:07
  • $\begingroup$ @BillDubuque It was reassuring seeing the phrases particular solution and homogeneous solution in your answer. $\quad$ (+1) for that and getting me to learn about mini-markdown in comments. $\endgroup$ – CopyPasteIt Jul 14 at 14:34

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