Haskell: Multiplikatives Inverse in einem Restklassenring

Das multiplikative Inverse einer Restklasse in einem Restklassenring kann man in Haskell mit folgendem Snippet berrechnen:

-- multiplicative inverse for a in Z  bZ
mulInverse :: (Int, Int) -> Int
mulInverse (a, m) =
  (x + m) `mod` m
  where
    (gcd, (x, y)) = euclid a m

-- returns (gcd(a,b), (x, y)) in eq ax + by = gcd(a,b)
euclid :: Int -> Int -> (Int, (Int, Int))
euclid 0 b = (b, (0, 1))
euclid a b = 
  (gcd, (y - (x*(b `div` a)), x))
  where
    (gcd, (x, y)) = euclid (b `mod` a) a

Beispiel: Das multiplikative Inverse für 8 im Restklassenring Z / 21 Z ist 8.

$ ghci mulInverse.hs
*Main> mulInverse (8, 21)
8