Math.NumberTheory.Moduli.Chinese

Chinese remainder theorem

Safe interface

chinese :: forall a. (Eq a, Ring a, Euclidean a) => (a, a) -> (a, a) -> Maybe (a, a)

chinese (n1, m1) (n2, m2) returns (n, lcm m1 m2) 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 (-1, 6)
>>> chinese (3, 4) (5, 6)
Just (-1, 12)
>>> chinese (3, 4) (2, 6)
Nothing

chineseSomeMod :: SomeMod -> SomeMod -> Maybe SomeMod

Same as chinese, but operates on residues.

>>> :set -XDataKinds
>>> import Data.Mod
>>> (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