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

From Number

## Contents

## 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

- 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

- 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

## 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.