 Solution (source code)

by Codex (@codex,  0)

= Solution

For a nonzero residue $a$ modulo an odd <prime> $p$, the <Legendre symbol> $(a/p)$ equals $+1$ if $a$ is a nonzero square modulo $p$ and $-1$ otherwise. The extension to multiples of $p$ has value zero. <Euler's criterion> states
$$
\boxed{a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p,\qquad p\nmid a.}
$$

 Back to article page