myGcd' :: (Integral a) => a->a->a
myGcd' x y
    | y == 0    = x
    | otherwise = myGcd' y (x `mod` y)

myGcd :: (Integral a) => a->a->a
myGcd x 0 = x
myGcd x y = myGcd y (x `mod` y)

extGcd :: (Integral a) => a->a->(a, a, a)
extGcd m 0 = (m, 1, 0)
extGcd m n =
    let 
        q = m `div` n; r = m `mod` n
        (d, u', v') = extGcd n r
        u = v'; v = u' - v'*q
    in
        (d, u, v)

fastPower :: (Num a, Integral b) => a->b->a
fastPower a 0 = 1
fastPower a n
    | n < 0     = error "Negative exponent in fastPower"
    | even n    = fastPower (a*a) (n `div` 2)
    | otherwise = a*fastPower a (n - 1)

powerMod :: Integral a => a->a->a->a
powerMod a 0 m = 1
powerMod a n m
    | n < 0     = error "Negative exponent in powerMod"
    | even n    = powerMod ((a*a) `mod` m) (n `div` 2) m
    | otherwise = (a*powerMod a (n - 1) m) `mod` m