# Dirichlet's theorem for modulus four

## Statement

Suppose  is an odd natural number. Then, there exist infinitely many prime numbers  such that:

.

## Proof

We need to check two congruence classes modulo : the congruence class of  and the congruence class of .

### The congruence class of  modulo 

By fact (2),  is a quadratic residue modulo  if and only if . In particular, a prime  can divide  for some natural number  if and only if .

Consider now the polynomial . For any natural number , all prime divisors of  are congruent to  modulo . By fact (3), there are infinitely many pairwise relatively prime values of , so we get infinitely many primes that are congruent to  modulo .

### Congruence class of  modulo 

By fact (1),  is a quadratic residue modulo  if and only if . In particular, a prime  can divide  for some natural number  if and only if .

Consider now the polynomial . For any natural number , all prime divisors of  are congruent to . However,  itself is  modulo , so  must have at least one prime divisor that is  modulo . By fact (3), there are infinitely many pairwise relatively prime values of , yielding infinitely many distinct primes that are  modulo . In particular, all these primes are  modulo .