Important: The numtheory package has been deprecated.  Use the superseding command NumberTheory[LegendreSymbol] instead.

The legendre(a, p) function computes the Legendre symbol $L\left(\frac{a}{p}\right)$ of a and p, which is defined to be $1$ if a is a quadratic residue $\mathbf{mod}p$, $\mathrm{-1}$ if a is a quadratic non-residue $\mathbf{mod}p$, and $0$ if a is congruent to $0\mathbf{mod}p$. The number a is a quadratic residue mod p if it is not a multiple of p and has a square root $\mathbf{mod}p$, that is, there is an integer $c$ such that $c^2$ is congruent to $a\mathbf{mod}p$. The number a is a quadratic non-residue mod p if it is not a multiple of p and does not have a square root $\mathbf{mod}p$.

Note: The legendre routine returns unevaluated if the given algebraic arguments are not of the types specified above.

The command with(numtheory,legendre) allows the use of the abbreviated form of this command.

$\mathrm{with}\left(\mathrm{numtheory}\right)\:$

$\mathrm{legendre}\left(74\,101\right)$

$\mathrm{-1}$

$\mathrm{legendre}\left(3\,73\right)$

$1$

$\mathrm{legendre}\left(22\,11\right)$

$0$

$\mathrm{legendre}\left(5\,2\right)$

$\mathrm{-1}$

$\mathrm{legendre}\left(-2342\,1901\right)$

$1$

$\mathrm{legendre}\left(a\,p\right)$

$\mathrm{legendre}\left(a\,p\right)$