text: 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  of quotients and a sequence  of remainders such that
  It is the main property of Euclidean division that the inequalities on the right define uniquely  and  from  and
  The computation stops when one reaches a remainder  which is zero; the greatest common divisor is then the last non zero remainder
  The extended Euclidean algorithm proceeds similarly, but adds two other sequences, as follows
  The computation also stops when  and gives
  is the greatest common divisor of the input  and
  The Bézout coefficients are  and  that is
  The quotients of a and b by their greatest common divisor are given  by  and
  Moreover, if a and b are both positive and , then
  for  where  denotes the integral part of , that is the greatest integer not greater than .
  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.