Thursday, March 9, 2017

elementary number theory - 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?


Answer



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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...