= Euler's criterion
{c}
{title2=$a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p$}
{wiki}
For an <odd prime> $p$ and $p\nmid a$, Euler's criterion identifies the <Legendre symbol> by <modular exponentiation>:
$$
a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p.
$$
Thus a <quadratic residue> gives one and a <quadratic nonresidue> gives minus one, represented by $p-1$ if a nonnegative <remainder> is used. The formula also holds when $p\mid a$, because $(p-1)/2>0$ and both sides are zero modulo $p$.<Quadratic Residues by Ben Lynn>[Ben Lynn, Quadratic Residues, Euler's Criterion and The Legendre Symbol: exponent test and the zero value]{ref}
For example, modulo seven the exponent is three: $2^3\equiv1$ confirms that two is a <quadratic residue>, while $3^3\equiv6\equiv-1$ confirms that three is a <quadratic nonresidue>. Modulo eleven the exponent is five, and $2^5=32\equiv10\equiv-1$ confirms that two is a <quadratic nonresidue>. The test answers whether a <square root> exists; it does not itself return the roots $3,4$ of $x^2\equiv2\pmod7$.
A short proof needs only <Fermat's little theorem> and the <root bound for a polynomial>. Put $m=(p-1)/2$. If $a=x^2\ne0$ in the <prime field>, then $a^m=x^{p-1}=1$. There are already $m$ such <quadratic residues>. The nonzero <polynomial> $T^m-1$ has <polynomial degree> $m$, so it has no other <polynomial roots>. Finally, for every nonzero $a$, <Fermat's little theorem> gives $(a^m)^2=a^{p-1}=1$. Factoring $(a^m-1)(a^m+1)=0$ in the <field> shows $a^m\in\{1,-1\}$; every <quadratic nonresidue> must take the remaining value $-1$. This proves the criterion without first finding a <primitive root>.
For a larger original example, decide whether seven is a <quadratic residue> modulo the <prime number> $101$. <Exponentiation by squaring> computes the required power without listing fifty squares:
$$
\begin{aligned}
7^2&\equiv49,&7^4&\equiv78,&7^8&\equiv24,\\
7^{16}&\equiv71,&7^{32}&\equiv92,\\
7^{50}&=7^{32}7^{16}7^2\equiv92\cdot71\cdot49\equiv-1\pmod{101}.
\end{aligned}
$$
Therefore $(7/101)=-1$ and $x^2\equiv7\pmod{101}$ has no solution. Each intermediate product is reduced modulo $101$, as in <modular exponentiation>. The advantage is that <exponentiation by squaring> uses a number of <multiplications> proportional to the <binary digit> length of the exponent rather than testing every potential <square root>.
The <odd prime> hypothesis is essential. For the composite modulus nine, $2^{(9-1)/2}=2^4\equiv7\pmod9$, which is neither one nor minus one. Although four is a nonzero square modulo nine, $4^4\equiv4\pmod9$, so even the square-to-one implication fails. The <Jacobi symbol> and <Euler pseudoprime> discuss different questions for odd composite moduli; they do not make this a universal square test.
Back to article page