 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