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

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 .

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