Legendre

Returns the Legendre symbol. Let $p$ be an odd prime. An integer $a$ is a quadratic residue modulo $p$ if it is congruent to a perfect square modulo $p$, and is a quadratic nonresidue modulo $p$ otherwise. The Legendre symbol is a function of $a$ and $p$ defined as

$\left(\frac{a}{p}\right)=\left\{\begin{array}{l}\begin{array}{l}-1\mathrm{if}a\not\equiv 0(\mathrm{mod}p)\mathrm{and}\mathrm{there}\mathrm{is}\mathrm{no}\mathrm{integer}x:a\equiv x^2\mathit{}(\mathrm{mod}p),\\ 0\mathrm{if}a\equiv 0(\mathrm{mod}p),\end{array}\\ 1\mathrm{if}a\not\equiv 0(\mathrm{mod}p)\mathrm{and}\mathrm{for}\mathrm{some}\mathrm{integer}x:a\equiv x^2(\mathrm{mod}p).\end{array}\right.$

legendre(Integer, Integer)

Description

Given an integer $a$ and an odd prime $p$, computes the Legendre symbol $\left(\frac{a}{p}\right)$.