def extended_gcd(p, q):
 (a, b) = (p, q)
 if (a < 0):
  a = ((-1) * a)
 if (b < 0):
  b = ((-1) * b)
 x0 = 0
 y1 = 0
 x1 = 1
 y0 = 1
 while (b != 0):
  quotient = (a // b)
  (a, b) = (b, (a % b))
  (x1, x0) = ((x0 - (quotient * x1)), x1)
  (y1, y0) = ((y0 - (quotient * y1)), y1)
 if (p < 0):
  y0 = ((-1) * y0)
 if (q < 0):
  x0 = ((-1) * x0)
 return (y0, x0)

def extended_gcd ( p , q ) : ( a , b ) = ( p , q ) if ( a < 0 ) : a = ( ( - 1 ) * a ) if ( b < 0 ) : b = ( ( - 1 ) * b ) x0 = 0 y1 = 0 x1 = 1 y0 = 1 while ( b != 0 ) : quotient = ( a // b ) ( a , b ) = ( b , ( a % b ) ) ( x1 , x0 ) = ( ( x0 - ( quotient * x1 ) ) , x1 ) ( y1 , y0 ) = ( ( y0 - ( quotient * y1 ) ) , y1 ) if ( p < 0 ) : y0 = ( ( - 1 ) * y0 ) if ( q < 0 ) : x0 = ( ( - 1 ) * x0 ) return ( y0 , x0 )
returns a tuple such that r = gcd = ia + jb .