text: (old_t, t) := (t, old_t − quotient × t)
  output "Bézout coefficients:", (old_s, old_t)
  output "greatest common divisor:", old_r
  output "quotients by the gcd:", (t, s)
  The quotients of a and b by their greatest common divisor, which is output, may have an incorrect sign. This is easy to correct at the end of the computation but has not been done here for simplifying the code. Similarly, if either a or b is zero and the other is negative, the greatest common divisor that is output is negative, and all the signs of the output must be changed.
  Finally, notice that in Bézout's identity, , one can solve for  given . Thus, an optimization to the above algorithm is to compute only the  sequence (which yields the Bézout coefficient ), and then compute  at the end:
  function extended_gcd(a, b)
  s := 0;    old_s := 1
  r := b;    old_r := a
  while r ≠ 0 do
  quotient := old_r div r
  (old_r, r) := (r, old_r − quotient × r)
  (old_s, s) := (s, old_s − quotient × s)
  if b ≠ 0 then
  bezout_t := (old_r − old_s × a) div b
  else
  bezout_t := 0
  output "Bézout coefficients:", (old_s, bezout_t)
  output "greatest common divisor:", old_r