TOPICS
Search

Legendre Symbol

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The Legendre symbol is a number theoretic function (a/p) which is defined to be equal to +/-1 depending on whether a is a quadratic residue modulo p. The definition is sometimes generalized to have value 0 if p|a,

(a/p)=(a|p)={0 if p|a; 1 if a is a quadratic residue modulo p; -1 if a is a quadratic nonresidue modulo p.
(1)

If p is an odd prime, then the Jacobi symbol reduces to the Legendre symbol. The Legendre symbol is implemented in the Wolfram Language via the Jacobi symbol, JacobiSymbol[a, p].

The Legendre symbol obeys the identity

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

Particular identities include

((-1)/p)=(-1)^((p-1)/2)
(3)
(2/p)=(-1)^((p^2-1)/8)
(4)
((-3)/p)={1 if p=1 (mod 6); -1 if p=5 (mod 6)
(5)
(5/p)={1 if p=1,9 (mod 10); -1 if p=3,7 (mod 10)
(6)

(Nagell 1951, p. 144), as well as the general

(q/p)=(p/q)(-1)^([(p-1)/2][(q-1)/2])
(7)

when p and q are both odd primes.

In general,

(a/p)=a^((p-1)/2) (mod p)
(8)

if p is an odd prime.

See also

Jacobi Symbol, Kronecker Symbol, Quadratic Reciprocity Theorem, Quadratic Residue

Explore with Wolfram|Alpha

References

Guy, R. K. "Quadratic Residues. Schur's Conjecture." §F5 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 244-245, 1994.Hardy, G. H. and Wright, E. M. "Quadratic Residues." §6.5 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 67-68, 1979.Jones, G. A. and Jones, J. M. "The Legendre Symbol." §7.3 in Elementary Number Theory. Berlin: Springer-Verlag, pp. 123-129, 1998.Nagell, T. "Euler's Criterion and Legendre's Symbol." §38 in Introduction to Number Theory. New York: Wiley, pp. 133-136, 1951.Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 33-34 and 40-42, 1993.

Referenced on Wolfram|Alpha

Legendre Symbol

Cite this as:

Weisstein, Eric W. "Legendre Symbol." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LegendreSymbol.html

Subject classifications