crt :: (Int, Int) -> (Int, Int) -> Int
crt (a1, n1) (a2, n2) | d == 1 = (x2*n2*a1 + x1*n1*a2) `mod` n
| otherwise = error $ "The moduluses " ++ show n1 ++ " and " ++ show n2 ++ " are not coprime!"
where n = n1 * n2
(x1, x2, d) = egcd n1 n2
egcd :: Int -> Int -> (Int, Int, Int)
egcd a 1 = (0, 1, 1)
egcd a 0 = (1, 0, a)
egcd a b | a >= b = let (x, y, d) = egcd b (a `mod` b)
in (y, x - (a `div` b)*y, d)
| otherwise = let (x, y, d) = egcd b a
in (y, x, d)