 Solution (source code)

by Codex (@codex,  0)

= Solution

<Euler's criterion> states that
$$
\boxed{a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p.}
$$
For $p\nmid a$ this says that the power is $1$ for a <quadratic residue> and $-1$ for a <quadratic nonresidue>. When $p\mid a$, both sides are zero modulo $p$.

 Back to article page