-- extended euclidean algorithm
-- pesco, 2009

ee :: Integer -> Integer -> (Integer, Integer, Integer)
ee a b
  | a<b = ee' (b,0,-1) (a,1,0)
  | otherwise = ee' (a,1,0) (b,0,-1)
  where
  ee' (r2,x2,y2) (r1,x1,y1)
    | r==0 = (r1,x1,y1)
    | otherwise = ee' (r1,x1,y1) (r,x,y)
    where
    (q,r) = quotRem r2 r1
    x = x2 - x1 * q
    y = y2 - y1 * q