Every integer that is not a perfect square is a quadratic nonresidue for infinitely many primes

From Number
Jump to: navigation, search

Statement

Suppose is an integer that is not a perfect square. Then, there are infinitely many primes such that is a quadratic nonresidue modulo .

Related facts and conjectures

Corollaries

Similar facts

Facts used

  1. Dirichlet's theorem on primes in arithmetic progressions
  2. Quadratic reciprocity
  3. Congruence condition for minus one to be a quadratic residue
  4. Congruence condition for two to be a quadratic residue

Proof

Proof idea

By a combination of facts (2), (3), and (4), we can show that whether or not is a quadratic residue modulo depends on whether lies in certain congruence classes modulo . Further, if is not a perfect square, there is at least one congruence class modulo such that is a quadratic nonresidue modulo any prime in that congruence class. Fact (1) now yields the infinitude.