UTM Ideals Varieties and Algorithm - Chapter 1 Section 5 Exercise 10

Problem:

Solution:

The key idea is to return more values in each call to GCD.

Function ExtendedGCD(f, g) = (A, B, h):
  if (degree(A) > degree(B)):
    return ExtendedGCD(g, f)
  else:
    (quotient, remainder) = divide(A, B)
    if (remainder == 0):
      # A - B * quotient = 0
      # A + B - B * quotient = B
      # A + B * (1 - quotient) = B
      return (1, 1-quotient, B)
    else
      (p, q, gcd) = GCD(B, remainder)
      # A - B * quotient = remainder
      # p * B + q * remainder = gcd
      # p * B + q * (A - B * quotient) = gcd
      # q * A + (p - q * quotient) * B = gcd
      return (q, p - q * quotient, gcd)

Now even my pseudocode are pythonic!