Copyright	(c) 2011 Daniel Fischer 2018 Andrew Lelechenko
License	MIT
Maintainer	Andrew Lelechenko <andrew.lelechenko@gmail.com>
Safe Haskell	None
Language	Haskell2010

Math.NumberTheory.Moduli.Chinese

Contents

Safe interface

Description

Chinese remainder theorem

Synopsis

chinese :: (Eq a, Ring a, Euclidean a) => (a, a) -> (a, a) -> Maybe (a, a)
chineseSomeMod :: SomeMod -> SomeMod -> Maybe SomeMod

Safe interface

chinese :: (Eq a, Ring a, Euclidean a) => (a, a) -> (a, a) -> Maybe (a, a) Source #

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 Source #

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