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

# sympy.ntheory.jacobi_symbol

All Samples(24)  |  Call(22)  |  Derive(0)  |  Import(2)
```Returns the product of the legendre_symbol(m, p)
for all the prime factors, p, of n.

Returns
=======

1. 0 if m cong 0 mod(n)
2. 1 if x**2 cong m mod(n) has a solution
3. -1 otherwise
(more...)
```

```        def jacobi_symbol(m, n):
"""
Returns the product of the legendre_symbol(m, p)
for all the prime factors, p, of n.

Returns
=======

1. 0 if m cong 0 mod(n)
2. 1 if x**2 cong m mod(n) has a solution
3. -1 otherwise

Examples
========

>>> from sympy.ntheory import jacobi_symbol, legendre_symbol
>>> from sympy import Mul, S
>>> jacobi_symbol(45, 77)
-1
>>> jacobi_symbol(60, 121)
1

The relationship between the jacobi_symbol and legendre_symbol can
be demonstrated as follows:

>>> L = legendre_symbol
>>> S(45).factors()
{3: 2, 5: 1}
>>> jacobi_symbol(7, 45) == L(7, 3)**2 * L(7, 5)**1
True

========

"""
m, n = as_int(m), as_int(n)
if not n % 2:
raise ValueError("n should be an odd integer")
if m < 0 or m > n:
m = m % n
if not m:
return int(n == 1)
if n == 1 or m == 1:
return 1
if igcd(m, n) != 1:
return 0

j = 1
s = trailing(m)
m = m >> s
if s % 2 and n % 8 in [3, 5]:
j *= -1

while m != 1:
if m % 4 == 3 and n % 4 == 3:
j *= -1
m, n = n % m, m
s = trailing(m)
m = m >> s
if s % 2 and n % 8 in [3, 5]:
j *= -1
return j
```

```from sympy.core.compatibility import long

from sympy.ntheory import isprime, n_order, is_primitive_root, \
is_quad_residue, legendre_symbol, jacobi_symbol, npartitions, totient, \
factorint, primefactors, divisors, randprime, nextprime, prevprime, \
```
```    raises(ValueError, lambda: legendre_symbol(2, 4))

assert jacobi_symbol(25, 41) == 1
assert jacobi_symbol(-23, 83) == -1
assert jacobi_symbol(3, 9) == 0
assert jacobi_symbol(42, 97) == -1
```

```from sympy.core.compatibility import long

from sympy.ntheory import isprime, n_order, is_primitive_root, \
is_quad_residue, legendre_symbol, jacobi_symbol, npartitions, totient, \
factorint, primefactors, divisors, randprime, nextprime, prevprime, \
```
```    raises(ValueError, lambda: legendre_symbol(2, 4))

assert jacobi_symbol(25, 41) == 1
assert jacobi_symbol(-23, 83) == -1
assert jacobi_symbol(3, 9) == 0
assert jacobi_symbol(42, 97) == -1
```