Did I find the right examples for you? yes no      Crawl my project      Python Jobs

# sympy.ntheory.modular.crt

All Samples(11)  |  Call(8)  |  Derive(0)  |  Import(3)
```Chinese Remainder Theorem.

The moduli in m are assumed to be pairwise coprime.  The output
is then an integer f, such that f = v_i mod m_i for each pair out
of v and m. If ``symmetric`` is False a positive integer will be
returned, else \|f\| will be less than or equal to the LCM of the
moduli, and thus f may be negative.

If the moduli are not co-prime the correct result will be returned
if/when the test of the result is found to be incorrect. This result(more...)
```

```        def crt(m, v, symmetric=False, check=True):
r"""Chinese Remainder Theorem.

The moduli in m are assumed to be pairwise coprime.  The output
is then an integer f, such that f = v_i mod m_i for each pair out
of v and m. If ``symmetric`` is False a positive integer will be
returned, else \|f\| will be less than or equal to the LCM of the
moduli, and thus f may be negative.

If the moduli are not co-prime the correct result will be returned
if/when the test of the result is found to be incorrect. This result
will be None if there is no solution.

The keyword ``check`` can be set to False if it is known that the moduli
are coprime.

As an example consider a set of residues ``U = [49, 76, 65]``
and a set of moduli ``M = [99, 97, 95]``. Then we have::

>>> from sympy.ntheory.modular import crt, solve_congruence

>>> crt([99, 97, 95], [49, 76, 65])
(639985, 912285)

This is the correct result because::

>>> [639985 % m for m in [99, 97, 95]]
[49, 76, 65]

If the moduli are not co-prime, you may receive an incorrect result
if you use ``check=False``:

>>> crt([12, 6, 17], [3, 4, 2], check=False)
(954, 1224)
>>> [954 % m for m in [12, 6, 17]]
[6, 0, 2]
>>> crt([12, 6, 17], [3, 4, 2]) is None
True
>>> crt([3, 6], [2, 5])
(5, 6)

Note: the order of gf_crt's arguments is reversed relative to crt,
and that solve_congruence takes residue, modulus pairs.

Programmer's note: rather than checking that all pairs of moduli share
no GCD (an O(n**2) test) and rather than factoring all moduli and seeing
that there is no factor in common, a check that the result gives the
indicated residuals is performed -- an O(n) operation.

========

solve_congruence
sympy.polys.galoistools.gf_crt : low level crt routine used by this routine
"""
if check:
m = list(map(as_int, m))
v = list(map(as_int, v))

result = gf_crt(v, m, ZZ)
mm = prod(m)

if check:
if not all(v % m == result % m for v, m in zip(v, m)):
result = solve_congruence(*list(zip(v, m)),
check=False, symmetric=symmetric)
if result is None:
return result
result, mm = result

if symmetric:
return symmetric_residue(result, mm), mm
return result, mm
```

```from sympy.ntheory.primetest import _mr_safe_helper, mr
from sympy.ntheory.bbp_pi import pi_hex_digits
from sympy.ntheory.modular import crt, crt1, crt2, solve_congruence

from sympy.polys.domains import ZZ
```
```    def mcrt(m, v, r, symmetric=False):
assert crt(m, v, symmetric) == r
mm, e, s = crt1(m)
assert crt2(m, v, mm, e, s, symmetric) == (r, mm)

```
```    mcrt([2, 3, 5], [-1, -1, -1], 2*3*5 - 1, False)

assert crt([656, 350], [811, 133], symmetric=True) == (-56917, 114800)

```

```from sympy.ntheory.primetest import _mr_safe_helper, mr
from sympy.ntheory.bbp_pi import pi_hex_digits
from sympy.ntheory.modular import crt, crt1, crt2, solve_congruence

from sympy.utilities.pytest import raises
```
```    def mcrt(m, v, r, symmetric=False):
assert crt(m, v, symmetric) == r
mm, e, s = crt1(m)
assert crt2(m, v, mm, e, s, symmetric) == (r, mm)

```
```    mcrt([2, 3, 5], [-1, -1, -1], 2*3*5 - 1, False)

assert crt([656, 350], [811, 133], symmetric=True) == (-56917, 114800)

```

```from sympy import factorial as fac

from sympy.ntheory.modular import crt, crt1, crt2

def test_trailing():
```
```def test_crt():
assert crt([2, 3, 5], [0, 0, 0]) == 0
assert crt([2, 3, 5], [1, 1, 1]) == 1

assert crt([2, 3, 5], [-1, -1, -1], True) == -1
assert crt([2, 3, 5], [-1, -1, -1], False) == 2*3*5 - 1
```