Congruence condition for two to be a quadratic residue

Statement

Suppose $p$ is an odd prime. Then:

• $2$ is a quadratic residue modulo $p$ if and only if $p\equiv \pm 1(\mathrm{mod}8)$, i.e., $p\equiv 1(\mathrm{mod}8)$ or $p\equiv 7(\mathrm{mod}8)$.
• $2$ is a quadratic nonresidue modulo $p$ if and only if $p\equiv \pm 3(\mathrm{mod}8)$, i.e, $p\equiv 3(\mathrm{mod}8)$ or $p\equiv 5(\mathrm{mod}8)$.

Related facts

Similar facts

• Congruence condition for minus one to be a quadratic residue
• Quadratic reciprocity

Applications

• Every integer that is not a perfect square is a quadratic nonresidue for infinitely many primes
• Every integer is a quadratic residue for infinitely many primes
• Safe prime has plus or minus two as a primitive root