[Python] ExtendedGcd code snippet

ExtendedGcd code snippet:

def ExtendedGcd(a, b):
  """
  Extended Euclidean algorithm.

  Computes, in addition to the greatest common divisor of integers a and b,
  also the coefficients of Bezout's identity, which are integers x and y such
  that a x + b y = gcd(a, b).

  Args:
    a: An integer.
    b: An integer.

  Returns:
    A tuple (g, x, y) satisfying a x + b y = g.
  """
  if a == 0:
    return (b, 0, 1)
  else:
    g, y, x = ExtendedGcd(b % a, a)
    return (g, x - (b // a) * y, y)