from typing import Tuple


def extended_gcd(a: int, b: int) -> Tuple[int, int, int]:
  """Find the greatest common divisor using the extended Euclidean algorithm.

  Returns:
    A tuple (gcd, x, y) with the property that a * x + b * y = gcd.

  >>> extended_gcd(29, 71)
  (1, -22, 9)
  >>> (29 * -22) % 71
  1
  """
  prev_x, x = 1, 0
  prev_y, y = 0, 1
  while b:
    q = a // b
    x, prev_x = prev_x - q * x, x
    y, prev_y = prev_y - q * y, y
    a, b = b, a % b
  x, y = prev_x, prev_y
  return a, x, y