arithmoi-0.12.1.0: Efficient basic number-theoretic functions.

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

Math.NumberTheory.Moduli.Chinese

Contents

- Safe interface

Description

Chinese remainder theorem

Synopsis

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

# Safe interface

chinese :: forall a. (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