 Solution (source code)

by Codex (@codex,  0)

= Solution

<Euler's criterion> states that, for an odd prime $p$ and $p\nmid a$,
$$
\boxed{a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p.}
$$
Thus this power is congruent to one for a nonzero square and to minus one for a nonsquare. The congruence also holds when $p\mid a$ if both sides are taken to be zero.

 Back to article page