Every integer is a quadratic residue for infinitely many primes

From Number
Jump to: navigation, search

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

Other related facts

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 .