Every integer that is not a perfect square is a quadratic nonresidue for infinitely many primes
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
- 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
- Dirichlet's theorem on primes in arithmetic progressions
- Quadratic reciprocity
- Congruence condition for minus one to be a quadratic residue
- Congruence condition for two to be a quadratic residue
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.