Let's prove that there are infinitely many primes such that .
Let be a finite list of primes congruent to 3 mod 4, and construct a new integer
that is 3 mod 4, and not divisible by any of the 's, .
Note that is an odd integer, so it can only have prime factors that are 1 or 3 mod 4. Let's suppose that all its prime factors were 1 and 4. Then
so would also be 1 mod 4, but this is a contradiction, because our integer is 3 mod 4 by construction. So there must be at least one prime factor that is 3 mod 4. But since is not divisible by any , which are primes congruent to 3 mod 4, we have thus found a new prime that is not in our original list .
there must be an infinitude of primes that are congruent to .
Another special case is that there exists infinitely many primes such that . This case can be shown to be true in the same way, by constructing an integer , and following the same procedure above.
In fact, Dirichlet's theorem states that for , any coprime integers and , there exists infinitely many primes such that . His own proof, consisting of Dirichlet L-functions, is often considered to have contributed to the origins of Analytic Number Theory.