Solve a given system of congruences using Chinese Remainder Theorem (CRT)

chineseRemainder.hs

-- | Solve a given system of congruences using Chinese Remainder Theorem (CRT)
-- [(Integer, Integer)] = [(eq.1 residue, eq.1 modulo), (eq.2 residue, eq.2 modulo),..]
chineseRemainder :: [(Integer, Integer)] -> Maybe Integer
chineseRemainder congruences =
  (`mod` _N)
    .   sum
    .   hadamard _Ni
    .   hadamard residues
    <$> zipWithM getMi _Ni moduli
 where
  (residues, moduli) = unzip congruences
  _N                 = product moduli
  _Ni                = (_N `div`) <$> moduli
  hadamard           = zipWith (*)
  getMi a p | (a * inv) /% p == 1 = Just inv
            | otherwise           = Nothing
    where inv = a /% p
    
    
-- | Extended Euclidean algorithm based on Bezout's identity
-- ax + by = gcd(a, b), returns (x, y)
egcd :: Integer -> Integer -> (Integer, Integer)
egcd _ 0 = (1, 0)
egcd a b = (y, x - q * y)
 where
  (q, r) = quotRem a b
  (x, y) = egcd b r

-- | Reciprocal in Z/pZ
-- By Extended Euclidean algorithm: egcd(a, p) -> (x, y)
(/%) :: Integer -> Integer -> Integer
a /% p = fst $ egcd a p