4
$\begingroup$

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?

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – Brian M. Scott
    Oct 2, 2012 at 2:30
  • $\begingroup$ 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$ $\endgroup$
    – CodeKingPlusPlus
    Oct 2, 2012 at 3:00
  • $\begingroup$ 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. $\endgroup$
    – Brian M. Scott
    Oct 2, 2012 at 3:02
  • $\begingroup$ 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$ $\endgroup$
    – CodeKingPlusPlus
    Oct 2, 2012 at 12:32
  • $\begingroup$ 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$. $\endgroup$
    – Brian M. Scott
    Oct 2, 2012 at 19:43

1 Answer 1

Reset to default
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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