There are large number of different algorithms for gcd computation. First of all, it is the Shonhage type gcd algorithms. They are used for very large numbers and have the best asymptotic complexity in the worst case — $ O (n \log ^ 2 (n) \log (\log (n))) $. For lesser numbers, generalized binary algorithms are used. They are based on the $ k $ -ary reduction: $ \alpha \gcd (u, v) = \gcd (v, \frac{| au \pm bv |} {k}) $, integers $ u> v> 0 $, $ \gcd (u, k) = \gcd (v, k) = 1 $, $ \alpha \geqslant 1 $. We use $+$ or $-$ depending on the type of gcd algorithm. The main task is to select the coefficients $ a, b $ such that $ au + bv = 0 \bmod k $. The number $ k $ is usually chosen as a prime number or a power of a prime number. Unfortunately, spirious factors can accumulate during the computation, so $ \alpha \geqslant 1 $. If $ k = 2 ^ s $, then we obtain generalized binary algorithms. It's five times faster than the binary gcd algorithm. Sedjelmaci modified the Jebelean-Weber's algorithm, he removed spirious factors. Asymptotic complexity of the algorithm in the worst case is $ O (n ^ 2 / \log (n)) $.
Bezout Coefficients is a representation of gcd $ d $ of the numbers $ A, B $ of a linear combination $ Ax + By = d $, where $ x $ and $ y $ are integer numbers, called Bezout coefficients. In this paper we introduce the extended Jebelean–Weber–Sedjelmaci algorithm of two natural numbers, formulas and give examples that showing how to calculate inverse elements.
