Determine whether the following are quadratic residues of prime 37:
(a) 6
(b) 2
(c) 12
(d) 5
We'll be using Euler’s Criterion (7.5).
Let $p$ be an odd prime such that $p \not \mid a$. Then $a$ is a quadratic residue of $p$ if and only if $a^{\frac{p−1}{2}} \equiv 1 \pmod p$.
(a) $37 \not \mid 6$ and
$$ 6^{\frac{37-1}{2}} \equiv 6^{18} \equiv (6^3)^6 \equiv (31)^6 \equiv -1 \pmod {37} $$
Therefore 6 is not a quadratic residue of 37.
(b) $37 \not \mid 2$ and
$$ 2^{\frac{37-1}{2}} \equiv 2^{18} \equiv 262144 \equiv -1 \pmod {37} $$
Therefore 2 is not a quadratic residue of 37.
(c) $37 \not \mid 12$ and
$$ 12^{\frac{37-1}{2}} \equiv 12^{18} \equiv (12^3)^6 \equiv 26^6 \equiv 308915776 \equiv 1 \pmod {37} $$
And so 12 is a quadratic residue of 37.
(d) $37 \not \mid 5$ and
$$ 5^{\frac{37-1}{2}} \equiv 5^{18} \equiv (5^3)^6 \equiv 14^6 \equiv 7529536 \equiv -1 \pmod {37} $$
Therefore 5 is not a quadratic residue of 37.