Every integer is a quadratic residue for infinitely many primes

Statement

Let be a nonzero integer. Then, there are infinitely many primes such that is a quadratic residue modulo . (The statement also holds for , if we declare 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 such that divides for some natural number . We can exclude the primes that divide itself (if we follow the convention that is not considered a quadratic residue) and we still obtain that there are infinitely many primes for which is a quadratic residue.

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