Introduction
Welcome Ninjas! Do you want to know how to encode the information about whether a number given is a quadratic residue modulo an odd prime? This is implemented by Legendre and Jacobi symbols.
Are you interested in knowing more about Legendre and Jacobi symbols? Great! You are at the right place. Let us first start with the Legendre symbol.
Legendre Symbol
The Legendre symbol is a function that stores information about whether an integer is a quadratic residue modulo an odd prime. To make notation simpler, it is applied in the law of quadratic reciprocity. The Legendre symbol is an excellent tool for performing computations and providing answers related to quadratic residues.
Note  An integer r is called a quadratic residue modulo m in number theory if it is congruent to a perfect square modulo m; i.e., if there exists an integer y such that: y^{2} â‰¡ r (mod m).
Let â€˜pâ€™ be an odd prime and â€˜aâ€™ be an integer and . The Legendre symbol â€˜aâ€™ with respect to â€˜pâ€™ is defined by
1 if a â‰¡ 0 (mod p) and â€˜aâ€™ is a quadratic residue modulo p
(a/p) = 1 if a is the quadratic nonresidue modulo p
0 if a â‰¡ 0 (mod p)
Note  The Legendre symbol ap looks like a fraction, but itâ€™s not.
Example 1:
from sympy.ntheory import legendre_symbol
[legendre_symbol(i, 11) for i in range(11)]
Output: [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Example 2:
from sympy.ntheory import legendre_symbol
[legendre_symbol(i, 5) for i in range(5)]
Output: [0, 1, 1, 1, 1]
Properties

If "a" is an integer which is not divisible by "p" and "p" is an odd prime(Euler's criterion), then, a^{(p1)/2}= (a/p) (mod p)

If a â‰¡ b (mod p), then, (a/p) = (b/p)

(ab/p) = (a/p )( b/p )

(1/p) = 1^{(p1)/2}, so iff p â‰¡ 1 mod 4, it is 1.

(2/p) = 1^{(p}*^{p1)/8}, so for an odd prime p, only if p â‰¡ Â±1 mod 8, it is 1.
 (q/p)(p/q) = 1^{(p1)/2.(q1)/2}