Math.NumberTheory.Moduli.Chinese

Chinese remainder theorem

Safe interface

chinese :: forall a. (Integral a, GcdDomain a, Euclidean a) => (a, a) -> (a, a) -> Maybe a

chinese (n1, m1) (n2, m2) returns n such that n `mod` m1 == n1 and n `mod` m2 == n2, if exists. Moduli m1 and m2 are allowed to have common factors.

>>> chinese (1, 2) (2, 3)
Just 5
>>> chinese (3, 4) (5, 6)
Just 11
>>> chinese (3, 4) (2, 6)
Nothing

chineseCoprime :: (Integral a, Euclidean a) => (a, a) -> (a, a) -> Maybe a

chineseCoprime (n1, m1) (n2, m2) returns n such that n `mod` m1 == n1 and n `mod` m2 == n2. Moduli m1 and m2 must be coprime, otherwise Nothing is returned.

This function is slightly faster than chinese, but more restricted.

>>> chineseCoprime (1, 2) (2, 3)
Just 5
>>> chineseCoprime (3, 4) (5, 6)
Nothing -- moduli must be coprime

chineseSomeMod :: SomeMod -> SomeMod -> Maybe SomeMod

Same as chinese, but operates on residues.

>>> :set -XDataKinds
>>> import Math.NumberTheory.Moduli.Class
>>> (1 `modulo` 2) `chineseSomeMod` (2 `modulo` 3)
Just (5 `modulo` 6)
>>> (3 `modulo` 4) `chineseSomeMod` (5 `modulo` 6)
Just (11 `modulo` 12)
>>> (3 `modulo` 4) `chineseSomeMod` (2 `modulo` 6)
Nothing

chineseCoprimeSomeMod :: SomeMod -> SomeMod -> Maybe SomeMod

Same as chineseCoprime, but operates on residues.

>>> :set -XDataKinds
>>> import Math.NumberTheory.Moduli.Class
>>> (1 `modulo` 2) `chineseCoprimeSomeMod` (2 `modulo` 3)
Just (5 `modulo` 6)
>>> (3 `modulo` 4) `chineseCoprimeSomeMod` (5 `modulo` 6)
Nothing

Unsafe interface

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.