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

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

• Quadratic Diophantine equation that has a solution modulo every prime has an integer solution

Similar facts

• Artin's conjecture on primitive roots
• Every integer is a quadratic residue for infinitely many primes
• Every prime is the smallest quadratic nonresidue for infinitely many primes

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.