# Infinitely many primes $\equiv 2 \pmod 3$ proof correctness

I know I have already asked a question regarding this proof. However, I wanted to see if my reformulation of this proof (with my better understanding in my own words and after some time) is correct.

Prove: There are infinitely many primes with remainder $2$ when divided by $3$:

Proof: Suppose not. Suppose there are finitely many primes with remainder $2$ when divided by $3$. That is:

There are finitely many primes of the form $p = 3k+2$ for some $k\in \mathbb{Z}$. Thus, we can construct a list of these odd primes (to exclude 2) and take their product:

$N = p_1p_2\cdots p_r$ for some $r \in \mathbb{Z}$

Now consider $3N+2$:

We know that $3N+2 \in \mathbb{Z}$ and has a factorization into primes. We also know that since $3N+2$ is of the form $3\cdot(\text{some integer}) + 2$ there is at least one prime factor of $3N+2$ of the form $3\cdot(\text{some integer}) + 2$. We also know that none of the primes $p_1p_2,\ldots,p_r$ divide $3N+2$ because if they did we would have for some prime $p_i$ in our list:

$p_i\mid(3N+2) \land p_i\mid N \implies p_i\mid 2$ Which cannot happen since our list of primes excludes $2$. Thus we have the two contradicting statements:

There exists a prime factor of the form $3k+2$ and there is no prime factor (from our finite list $p_1,p_2,\ldots,p_r$) of the form $3k+2$. Therefore, the supposition is false and there are infinitely many primes with remainder $2$ when divided by $3$.

Is this correct?

-
Looks okay. The only place where you might want to include a little more detail is the statement that a number of the form $3k+2$ must have at least one prime factor of the same form. – Brian M. Scott Oct 2 '12 at 2:30
Wouldn't the intuition of the clarity just be the only possibilities for prime factors of $3N+2$ are $3k+1$ and $3k+2$. Since $3N+2$ has the $+2$ we need a $3k+2$ – CodeKingPlusPlus Oct 2 '12 at 3:00
No, you need a $3k+2$ because every product of numbers of the form $3k+1$ also has the form $3k+1$. But that’s a fact that you really ought to justify. – Brian M. Scott Oct 2 '12 at 3:02
Could you explain this more with what I wrote? My understanding in general is something of the form $3k+2$ only has prime factors of the form $3k+1$ and $3k+2$ – CodeKingPlusPlus Oct 2 '12 at 12:32
That’s true, but you need more than that: you need to show that it must have at least one prime factor of the form $3k+2$, that they can’t all be of the form $3k+1$. To prove this, show that the product of numbers of the form $3k+1$ is also of the form $3k+1$. – Brian M. Scott Oct 2 '12 at 19:43