Prove that there are infinitely many primes of the form $3m + 1$ without using Dirichlet’s Theorem.
Hint: You may find the result of question 5 helpful.
For the purpose of contradiction we assume there are a finite number $k$ of primes $p_1, p_2, \ldots, p_k$ of the form $3m+1$, where $m$ is some positive integer.
We construct a number $N$ as follows
$$ N = (p_1 \times p_2 \times \ldots p_k )^2 + 3 $$
This $N$ is of the form $3m+1$ for some integer $m$.
There are two cases for $N$, prime and composite. Let's consider each in turn.
Case $N$ prime
If $N$ is prime, then it is larger than any of the $p_1, p_2, \ldots, p_k$ primes.
We've established that $N$ is of the form $3m+1$. This contradicts the assumption that the only primes of the form $3m+1$ are $p_1, p_2, \ldots, p_k$.
Case $N$ composite
If $N$ is composite it has an odd prime factor $p$, and so
$$ (p_1 \times p_2 \times \ldots p_k)^2 \equiv -3 \pmod p $$
Exercise (7.4).5 tell us $(\frac{-3}{p})=1 \iff p \equiv 1 \pmod 6$. That is, $p=6k+1$ for some integer $k$. Rewriting as $p=3(2k)+1$ means $p$ is of the form $3m+1$.
This $p$ is not one of the $p_1, p_2, \ldots, p_k$ because none of these divide $N=(p_1 \times p_2 \times \ldots p_k)^2 + 3$. If one $p_i$ did divide $N$ then it would have to divide 3, a contradiction.
This $p$ contradicts the assumption that the only primes of the form $3m+1$ are $p_1, p_2, \ldots, p_k$.
Both cases for $N$ contradict the assumption there are a finite number of primes of the form $3m+1$, and so there are infinitely many primes of this form.