code: def extended_euclidean_algorithm(a, b):
      
      r0, r1 = a, b
      s0, s1 = 1, 0
      t0, t1 = 0, 1
      while r1 != 0:
          q = r0 // r1
          r0, r1 = r1, r0 - q*r1
          s0, s1 = s1, s0 - q*s1
          t0, t1 = t1, t0 - q*t1
      return r0, s0, t0
docs: Extended Euclidean algorithm
  
      Returns r, s, t such that r = s*a + t*b and r is gcd(a, b)
  
      See <https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm>