Math.NumberTheory.Moduli.Chinese

Chinese remainder theorem

Documentation

chineseRemainder :: [(Integer, Integer)] -> Maybe Integer

Given a list [(r_1,m_1), ..., (r_n,m_n)] of (residue,modulus) pairs, chineseRemainder calculates the solution to the simultaneous congruences

r ≡ r_k (mod m_k)

if all moduli are positive and pairwise coprime. Otherwise the result is Nothing regardless of whether a solution exists.

chineseRemainder2 :: (Integer, Integer) -> (Integer, Integer) -> Integer

chineseRemainder2 (r_1,m_1) (r_2,m_2) calculates the solution of

r ≡ r_k (mod m_k)

if m_1 and m_2 are coprime.