I wish to prove that there are infinitely many primes of the form $3k+1$, $k\in\mathbb{N}$.
Proving that there are infinitely many primes of the form $3k+2$ is simple using a proof analogous to that of Euclid. It goes as follows:
Suppose there are finitely many primes of the form $3k+2$ and let $S=\{p_1,p_2,…,p_j\}$ denote the finite set of all such primes. Now consider the number $n=3p_1p_2…p_j+2$.
$n$ is clearly of the form $3k+2$. If $n$ is prime, we have a contradiction. If $n$ is composite, it must be divisible by a prime number $q$ of the form $3k+2$ (One can list the possibilities to convince oneself of this). But clearly $gcd(n,p)=1$ for every $p\in S$, which implies that $q\notin S$ – a contradiction. Thus our assumption that the number of such primes is finite must be false.
The problem is that when one attempts to apply the same proof to primes of the form $3k+1$, one runs into the difficulty that $(3k+2)^2=9k^2+12k+4=3(3k^2+4k+1)+1$, and thus a composite number of the form $3k+1$ needn't necessarily be divisible by a prime of the same form.
Is there any way of adjusting the proof so that it works for primes of the form $3k+1$ or does the problem call for a completely different proof-method?
Best Answer
The usual proof of this uses the fact that any prime dividing a number of the form $f(n)=n^2+n+1$ has to be congruent to $0$ or $1$ modulo $3$. If $p\mid f(n)$ and $p\ne3$ then $n^3\equiv1\pmod p$ but $n\not\equiv1\pmod p$. This will contradict Lagrange's theorem applied to the multiplicative group $\Bbb F_p^\times$ of integers not divisible by $p$ modulo $p$.
Now do the usual trick of considering the prime factorisation of $f(n)$ when $n$ has a lot of prime factors you want to avoid.