Maths WorkshopMaths problems with full solutions
Exercise 1585Number theory › CongruencesOlympiadAdded 3 Nov 2026

Legendre symbol and Euler's criterion

#Legendre symbol#Euler criterion#quadratic reciprocity

Statement

Define the Legendre symbol (ap)\left(\frac{a}{p}\right) and state Euler's criterion.

Hint

(ap)=1\left(\frac{a}{p}\right)=1 if aa is a nonzero quadratic residue mod pp, −1-1 if a non-residue, 00 if p∣ap\mid a.

Show solutionHide solution

Solution

Definition. For pp odd prime and a∈Za\in\mathbb{Z}:
(ap)={1if a is a QR mod p, a≢0,−1if a is a QNR mod p,0if p∣a.\left(\frac{a}{p}\right)=\begin{cases}1&\text{if }a\text{ is a QR mod }p,\ a\not\equiv0,\\ -1&\text{if }a\text{ is a QNR mod }p,\\0&\text{if }p\mid a.\end{cases}

Euler's criterion. (ap)≡a(p−1)/2(modp)\left(\frac{a}{p}\right)\equiv a^{(p-1)/2}\pmod p.

Multiplicativity. (abp)=(ap)(bp)\left(\frac{ab}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right).

Conclusion. The Legendre symbol is a multiplicative homomorphism from Fp∗\mathbb{F}_p^* to {±1}\{\pm1\}.