Legendre symbol

Named after French mathematician Adrien-Marie Legendre (1752–1833), who introduced the symbol in 1798 in his work Essai sur la Théorie des Nombres ("Essay on the Theory of Numbers").

Legendre symbol (plural Legendre symbols)

1. (number theory) A mathematical function of an integer and a prime number, written ${\displaystyle \left({a \over p}\right)}$, which indicates whether a is a quadratic residue modulo p.
   • 1994, James K. Strayer, Elementary Number Theory, Waveland Press, 2002, Reissue, page 109,

     Our only method at present for the computation of Legendre symbols requires a possible consideration of ${\displaystyle \textstyle {\frac {p-1}{2}}}$ congruences (unless, of course, we are fortunate enough to encounter the desired quadratic residue along the way).

   • 2006, Neville Robbins, Beginning Number Theory, 2nd edition, Jones & Bartlett, page 195:

     The Jacobi symbol, which generalizes the Legendre symbol, sheds some additional light on how to determine whether (7.29) has solutions when m has two or more distinct prime factors.

   • 2013, Song Y. Yan, Number Theory for Computing, Springer, page 149:

     Jacobi symbols can be used to facilitate the calculation of Legendre symbols. In fact, Legendre symbols can be eventually calculated by Jacobi symbols [17]. That is, the Legendre symbol can be calculated as if it were a Jacobi symbol. For example, consider the Legendre symbol ${\displaystyle \left({\frac {335}{2999}}\right)}$ where 335 = 5·67 is not a prime (of course, 2999 is a prime, otherwise, it is not a Legendre symbol).

The symbol takes the values:

${\displaystyle \left({\frac {a}{p}}\right)={\begin{cases}-1&{\text{ if }}a{\text{ is a quadratic nonresidue modulo }}p,\\0&{\text{ if }}a\equiv 0{\pmod {p}},\\1&{\text{ if }}a{\text{ is a quadratic residue modulo }}p{\text{ and }}a\not \equiv 0{\pmod {p}}.\end{cases}}}$

It is generalised to composite numbers by the Jacobi symbol, which is identical in form and range of values and is defined as a product of Legendre symbols.

• Euler's criterion
• Jacobi symbol
• quadratic reciprocity