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$

3 Answers 3

3
$\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$
5
  • $\begingroup$ Why is contradiction? $\endgroup$ Jan 21, 2016 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, 2016 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$ Jan 21, 2016 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$ Jan 21, 2016 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, 2016 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$
5
  • $\begingroup$ Please tell any benefit of your approach of choosing $-1$ as residue class, rather than $2$. $\endgroup$
    – jiten
    Jan 29, 2018 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
    Jan 29, 2018 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, 2018 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, 2018 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
    Jan 30, 2018 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$
1
  • $\begingroup$ If possible elaborate. $\endgroup$
    – jiten
    Jan 29, 2018 at 23:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .