Prove that there are infinitely many primes of the form 6k

Prove that there are infinitely many primes of the form 6k + 5.

Solution

Lemma: If p > 3 is prime, then either p = 1 (mod 6) or p = 5 (mod 6).

Proof: The residue classes modulo 6 partition Z, so any z in Z satisfies a congruence z = n (mod 6) where n is in {0,1,...,5}. z is divisible by 6 if n = 0, 2 if n = 2, 3 if n = 3, and 2 if n = 4. These cases cover the primes z = 2 and z = 3; if z > 3 is prime, it follows that n = 1 or n = 5, i.e., z = 1 (mod 6) or z = 5 (mod 6).

Now suppose there are only finitely many primes congruent to 5 modulo 6, say p_1, ..., p_k. Write M for p_1 * p_2 * ... * p_k and put N = 6M - 1. Now N = 5 (mod 6). If p is a prime divisor of 6 and p | N, then p | N - 6M = 1, a contradiction. This means that 2 and 3 are not prime factors of N. Thus it follows from the lemma that every prime p | N is either 1 or 5 mod 6. If every such prime is 1 mod 6, then N would be as well, a contradiction, so there is some prime p | N that is congruent to 5 mod 6.

Now if p = p_i for some i in {1,...,k}, then p | 6M and p | N, so p | 6M - N = 1, which is impossible. Thus the list p_1, ..., p_k was not exhaustive as supposed, so there are infinitely many primes of the form 6k + 5.