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