Legendre Symbol — Leandro Junes

Inputs

Integer

a

Any integer.

Odd prime

p

Odd prime greater than 2.

The modulus is checked with the site's primality classifier: below $3.3\times10^{{24}}$ the answer is exact, above it $p$ is only a probable prime and the result is labeled as assuming $p$ is prime. Computation runs locally in your browser.

Try

Result

—

Solution steps

—

Method

For an odd prime $p$ the Legendre symbol is

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

The value 1 means a nonzero quadratic residue: some integer $x$ satisfies $x^{2}\equiv a\pmod p$ . This calculator decides whether such an $x$ exists; it does not compute it.

Euler's criterion. If $p\nmid a$ , Fermat's theorem gives $a^{p-1}\equiv 1\pmod p$ , and the half-power refines it:

a^{(p-1)/2}\equiv\left(\frac{a}{p}\right)\pmod p.

So the half-power is 1 for a quadratic residue and −1 for a nonresidue. The calculator reduces $a$ modulo $p$ , handles $p\mid a$ and $a\equiv 1$ directly, and otherwise computes $a_0^{(p-1)/2}\bmod p$ by modular exponentiation. For a prime $p$ the residue is always 1 or $p-1$ ; any other residue proves that $p$ is composite, and then no symbol value is given.

Exact or conditional. If $p$ is below $3.3\times10^{24}$ it is proven prime and the answer is exact. Above that the site's classifier only establishes a probable prime, and the result is reported as assuming $p$ is prime.

Supplementary laws.

\left(\frac{-1}{p}\right)=(-1)^{(p-1)/2}=\begin{cases}1,&p\equiv 1\pmod 4,\\ -1,&p\equiv 3\pmod 4,\end{cases}

\left(\frac{2}{p}\right)=(-1)^{(p^{2}-1)/8}=\begin{cases}1,&p\equiv 1,7\pmod 8,\\ -1,&p\equiv 3,5\pmod 8.\end{cases}

Quadratic reciprocity. For distinct odd primes $p$ and $q$ :

\left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{(p-1)(q-1)}{4}}.

Equivalently $\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)$ unless both primes are congruent to 3 modulo 4, in which case the sign changes. It is not used by this calculator.

Group-theory view. The group of units $(\mathbb{Z}/p\mathbb{Z})^\times$ has order $p-1$ . The nonzero squares form a subgroup of index 2, so they contain $(p-1)/2$ elements: exactly half of the nonzero residue classes are quadratic residues. If $g$ is a primitive root modulo $p$ , then $\left(\frac{g}{p}\right)=-1$ , because $g$ has order $p-1$ and cannot lie in a subgroup of order $(p-1)/2$ .