Extended Euclidean algorithm

Uncommon card · No. 175912

In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that a x + b y = gcd ( a , b ) {\displaystyle ax+by=\gcd(a,b)} ; it is generally denoted as xgcd ⁡ ( a , b ) {\displaystyle \operatorname {xgcd} (a,b)} . This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs. It allows one to compute also, with almost no extra cost, the quotients of a and b by their greatest common divisor. Extended Euclidean algorithm also refers to a very similar algorithm for computing the polynomial...

Read on Wikipedia