Every integer is a quadratic residue for infinitely many primes

Statement

Let $a$ be a nonzero integer. Then, there are infinitely many primes $p$ such that $a$ is a quadratic residue modulo $p$. (The statement also holds for $a=0$, if we declare $0$ to be a quadratic residue).

Related facts

Stronger facts

• Every integer is a m-adic residue for infinitely many primes

Other related facts

• Artin's conjecture on primitive roots
• Every integer that is not a perfect square is a quadratic nonresidue for infinitely many primes
• Dirichlet's theorem on primes in arithmetic progressions

Facts used

1. Set of prime divisors of values of nonconstant polynomial with integer coefficients is infinite

Proof

By fact (1), there are infinitely many primes $p$ such that $p$ divides $n^{2}-a$ for some natural number $n$. We can exclude the primes that divide $a$ itself (if we follow the convention that $0$ is not considered a quadratic residue) and we still obtain that there are infinitely many primes $p$ for which $a$ is a quadratic residue.

Note that this proof generalizes to $m$-adic residues for any $m$.