Extended Euclidean algorithm
Description

The standard Euclidean algorithm proceeds by a succession of Euclidean divisions whose quotients are not used. Only the remainders are kept. For the extended algorithm, the successive quotients are used. More precisely, the standard Euclidean algorithm with a and b as input, consists of computing a sequence q 1, …, q k {\displaystyle q_{1},\ldots,q_{k}} of quotients and a sequence r 0, …, r k + 1 {\displaystyle r_{0},\ldots,r_{k+1}} of remainders such that

It is the main property of Euclidean division that the inequalities on the right define uniquely q i {\displaystyle q_{i}} and r i + 1 {\displaystyle r_{i+1}} from r i − 1 {\displaystyle r_{i-1}} and r i. {\displaystyle r_{i}.}

The computation stops when one reaches a remainder r k + 1 {\displaystyle r_{k+1}} which is zero; the greatest common divisor is then the last non zero remainder r k. {\displaystyle r_{k}.}

The extended Euclidean algorithm proceeds similarly, but adds two other sequences, as follows

The computation also stops when r k + 1 = 0 {\displaystyle r_{k+1}=0} and gives

Moreover, if a and b are both positive and gcd (a, b) ≠ min (a, b) {\displaystyle \gcd(a,b)\neq \min(a,b)}, then

for 0 ≤ i ≤ k, {\displaystyle 0\leq i\leq k,} where ⌊ x ⌋ {\displaystyle \lfloor x\rfloor } denotes the integral part of x, that is the greatest integer not greater than x.

This implies that the pair of Bézout's coefficients provided by the extended Euclidean algorithm is the minimal pair of Bézout coefficients, as being the unique pair satisfying both above inequalities.

Also it means that the algorithm can be done without integer overflow by a computer program using integers of a fixed size that is larger than that of a and b.
length_constraints:number_sentences[7], keywords:letter_frequency, combination:two_responses