Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 3 down vote accepted

Just as when Euclid's proof is erroneously reported (by Dirichlet, G. H. Hardy, and others) to be a proof by contradiction, your proof is more complicated than it needs to be. Instead of supposing that only finitely many exist, just say you have some set of finitely many, then go through your argument to show you can extend it to a larger finite set.

Other than that I think you're OK.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.