4
$\begingroup$

Prove that there are infinitely many primes of theform $3k+2$ I tried so: Let $$A= \left\{ p \in \mathbb{P} : \; p=3k+2 \right\}$$ Suppose, that the set $A$ is finite, i.e. $$A= \left\{ p_1 , p_2, \ldots , p_k \right\}$$ Let $$M=3 p_1 p_2, \ldots p_k+2$$ Then $M$ is of the form $3k+2$ Since $M>1$, then there exists prime $q$ such that $q\mid M$. We show that $M$ has prime divisor of the form $3k+2$. Suppose that every prime divisor of $M$ is of the form $3k+1$. Fundamental theorem of arithmetic we have that $M= q_1 q_2 \ldots q_s$ where for each $i$ $q_i$ is of the form $3k+1$. Since for each $i$ $q_i$ is of the form $3k+1$, then $$M= q_1 q_2 \ldots q_s$$ is of the form $3k+1$, contradiction because $M$ is of the form $3k+2$. Thus there exists prime $q$ of the form $$3k+2$$ and $q\mid M$. Thus there exists $i \in \left\{ 1, \ldots ,k\right\}$ such that $q=p_i$ but $q\mid M$, i.e. $p_i \mid M$, but $p_i \mid M=3 p_1 p_2, \ldots p_k+2$ and $p_i \mid 3 p_1 p_2, \ldots p_k$, contradiction. Thus $A$ is infinite. I have problem, because don't get a contradiction when $p_i=2$, but this proof is correct for primes of the form $4k-1$ and $6k-1$. Please help me.

$\endgroup$
2
$\begingroup$

Don't put the prime number $2$ in $M$. That is, if $A = \{ 2, p_2,p_3,...,p_n \}$, define $M = 3p_2p_3...p_n + 2$. Then, $ 2 \not| M$ and your argument shows that $M$ is neither in $A$ nor is divisible by any prime in $A$, a contradiction.

$\endgroup$
  • $\begingroup$ Why is contradiction? $\endgroup$ – george_smile Jan 21 '16 at 17:58
  • 1
    $\begingroup$ In my opinion, it is not really a proof by contradiction. You simply prove that any finite list of primes of the form $3k+2$ is incomplete. $\endgroup$ – Bernard Jan 21 '16 at 17:59
  • $\begingroup$ On one hand, $M$ is of the form $3k+2$ and you have shown that it must be divisible by a prime of the form $3k+2$, that is, a prime in $A$. But it is not: it is not divisible by 2 since M is odd (all prime numbers other than 2 are odd) and is not divisible by any other prime in $A$ by construction. $\endgroup$ – TopologicalGuy Jan 21 '16 at 18:02
  • $\begingroup$ @Bernard: You can see it either way. Since the OP has started "suppose that the list of ALL the primes of the form $3k+1$ is finite", it is a proof by contradiction, since the argument implies that there exists a prime of the form $3k+1$ not in the list. Of course you can also say that given any finite list of primes of the form $3k+1$ you can construct another one that is not in the list, and then it is not a proof by contradiction. $\endgroup$ – TopologicalGuy Jan 21 '16 at 18:04
  • 1
    $\begingroup$ @TopologicalGuy: What I meant is there are many so-called proofs by contradiction, which when analysed to some depth are not by contradiction, but, for instance, by contrapositive. As proofs by contradiction are not quite satisfactory proofs for beginners, I tend to prefer other proofs when possible. $\endgroup$ – Bernard Jan 21 '16 at 18:09
1
$\begingroup$

Try replacing your definition of $M = 3p_1p_2\cdots p_k + 2$ with $M = 3p_1p_2\cdots p_k - 1$. The argument still works as before, because the only thing you use is that $M \equiv 2 \textrm{ mod } 3$.

$\endgroup$
  • $\begingroup$ Please tell any benefit of your approach of choosing $-1$ as residue class, rather than $2$. $\endgroup$ – jiten Jan 29 '18 at 9:59
  • 1
    $\begingroup$ @jiten The benefit is that $M$ now is odd. The problem that the OP had was that they didn't get the desired contradiction since $M$ could be a power of two. $\endgroup$ – Marc Paul Jan 29 '18 at 10:22
  • $\begingroup$ Thanks for explaining that. But, have a bigger issue for which would also request your help, as this elementary proof, does work only when the primes used to construct $M$ can't be possibly constructed by other residue class' prime. Here, even factors of form $3k+2$ multiply together to get one of class $3k+1$, while odd factors yield $3k+2$. This fact is ignored in proof, & simply relies on all factors to be of exactly one class, and then shows by contradiction that $3k+1$ class factors cannot lead to one of $3k+2$. Why all factors need be of the same form? I request reason for that. $\endgroup$ – jiten Jan 29 '18 at 23:20
  • $\begingroup$ To elaborate further, if $N$ is an odd value, then all the factors should be considered of the form $3k+2$. While if $N$ is even, then an odd number of factors are to be considered of the form $3k+2$, while an even number or single factor is of the form $3k+1$. Is that sort of approach not possible? Of-course, that would fail the given approach, but what is the logic behind taking all factors of the same form. $\endgroup$ – jiten Jan 29 '18 at 23:29
  • $\begingroup$ @jiten I don't understand what you are saying. But I think it is better to post a new question, because comments are not for extended discussion. $\endgroup$ – Marc Paul Jan 30 '18 at 7:40
0
$\begingroup$

If $p_i = 2$ and $p_i | M$, $M$ is even, which I believe is a contradiction based on a particular construction of $M$.

$\endgroup$
  • $\begingroup$ If possible elaborate. $\endgroup$ – jiten Jan 29 '18 at 23:34

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.