(a) Prove that there are infinitely many primes of the form 3n + 1.
(b) Prove that there are infinitely many primes of the form 3n + 2.
(c) Explain why there are no primes of the form 3n + 3.
(a) The Dirichlet Theorem, noting that 3 and 1 are co-prime, tells us there are infinitely many primes of the form $3n+1$.
(b) The Dirichlet Theorem, noting that 3 and 2 are co-prime, tells us there are infinitely many primes of the form $3n+2$.
(c) Numbers of the form $3n+3 = 3(n+1)$ are divisible by 3 and so are not prime.