Eulers Criterion

Theorem

Let p be an odd prime and a an integer coprime to p. Then a is a quadratic residue modulo p (i.e. there exists a number k such that k² ≡ a (mod p)) if and only if

$a^{(p - 1) / 2} \equiv 1 \pmod p.$

Proof

Since the square-roots of 1 are $1, -1 \ (\text{mod} \ p) \ $, and since $a^{p-1}= 1 \ (\text{mod} \ p), a^{(p-1)/2} \ $ is either $1, -1 \ (\text{mod} \ p) \ $, and so Eulers criterion is equivalent to stating that a is a quadratic residue modulo p if and only if $a^{(p-1)/2} =1 \ (\text{mod} \ p) \ $.

We prove each direction separately.

($\Rightarrow \ $) Assume a is a quadratic residue modulo p. We pick k such that $k^2=a \ (\text{mod} \ p) \ $. Then

$a^{(p-1)/2}=k^{p-1}=1 \ (\text{mod} \ p) \ $.

by congruence of powers and Fermat's little theorem.

($\Leftarrow \ $) Assume $a^{(p-1)/2} =1 \ (\text{mod} \ p) \ $. Then let $y \ $ be a primitive root modulo p, so that a can be written as $y^j \ $. In particular, $y^{j(p-1)/2} =1 \ (\text{mod} \ p) \ $. By Fermat's little theorem, $p-1 | j(p-1)/2 \ $, so j must be even. Let $k=y^{j/2} \ (\text{mod} \ p) \ $. We have $k^2=y^j= a \ (\text{mod} \ p) \ $.