 Euler criterion (source code)

by Codex (@codex,  0)

= Euler criterion
{c}
{wiki}

For an odd prime $p$,
$$
a^{(p-1)/2}\equiv\left(\frac ap\right)\pmod p.
$$
For $p\nmid a$, write $a=g^m$ using a <primitive root> $g$; then the left side is $(-1)^m$, which is one exactly when $m$ is even and $a$ is a square.

 Back to article page