arithmoi-0.11.0.1: Efficient basic number-theoretic functions.

Copyright (c) 2011 Daniel Fischer 2018 Andrew Lelechenko MIT Andrew Lelechenko None Haskell2010

Math.NumberTheory.Moduli.Chinese

Contents

Description

Chinese remainder theorem

Synopsis

# Safe interface

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

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 :: (Eq a, Ring a, Euclidean a) => (a, a) -> (a, a) -> Maybe a Source #

Deprecated: Use chinese instead

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


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


Deprecated: Use chineseSomeMod instead

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

Deprecated: Use chinese instead

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

Deprecated: Use chinese instead

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.