Take the 2-minute tour ×
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.

Are there infinitely many composites $n$ of the following form $n = 2 p_{k_1} p_{k_2} \cdots p_{k_n} + 1$?

In other words are the infinitely many composite numbers constructed using any choices of primes for Euclids proof?

P.S.: Modified the original question to include $2$; without $2$ it was trivially true. Apologies to those who gave answers.

share|improve this question
add comment

4 Answers

up vote 8 down vote accepted

As Eric Naslund makes clear, his proof can be adjusted to deal with the $2$, and most reasonable variants that involve a fixed number $n$ of terms. The following is a very elementary argument for a much weaker result.

Let $q_1,q_2,\dots, q_{n}$ be a non-empty list of odd primes such that the list contains an even number (possibly $0$) of primes of the form $6k-1$. Then $2q_1q_2\cdots q_{n}$ is congruent to $2$ modulo $3$, and hence $2q_1q_2\cdots q_{n}+1$ is divisible by $3$. Since this number is greater than $3$, it is composite.

As a variant, let $p_0=2$, $p_1=3$, $p_2=5$, and so on. Let $a_n=p_0p_2p_3\cdots p_n+1$. (Note that we are skipping the prime $3$.) Then the sequence $(a_n)$ contains infinitely many composite numbers.

The proof uses nothing more than Euclid's Theorem.

It can be proved, by a mild variant of Euclid's proof, that there are infinitely many primes of the form $6k-1$. (There are also infinitely many of the form $6k+1$, but the proof is a little harder.)

From the fact that there are infinitely many primes of the form $6k-1$, we can, by taking an even number of them, and if necessary adding $5$ to the list, produce, for any fixed $n>1$, infinitely many $n$-tuples $(q_1,q_2,\dots,q_n)$ of distinct primes such that $2q_1q_2\cdots q_n +1$ is composite. The fact that there are infinitely many primes of the form $6k+1$ gives us in addition the result for $n=1$.

Comment: The numbers $a_n=p_0p_2p_3\cdots p_n+1$ mentioned in the solution are close relatives of $b_n=p_0p_1p_2\cdots p_n+1$. But while the proof that the sequence $(a_n)$ has infinitely many composites was elementary, at this time it is not known whether the sequence $(b_n)$ has infinitely many composites.

share|improve this answer
    
This is probably the best answer for the OP. –  Eric Naslund Nov 23 '11 at 13:58
    
Did you intend to have a $+1$ in your definition of $a_n$? I mean, it's not really interesting that a product of $n$ primes is composite. –  Gerry Myerson Nov 23 '11 at 22:11
    
I don't think that this answers the question. The question is whether in the sequence constructed by Euclids proof an infinite number of composites occur, not if there are an infinite number of composites of the form product of primes plus one. –  Phira Nov 23 '11 at 23:08
    
@Gerry Myerson: Thanks, I have corrected the typos! Of course, it is $p_0p_2\cdots p_n+1$ that was meant. But the fact there are infinitely many composites with the $+1$ is not much harder than without. –  André Nicolas Nov 23 '11 at 23:29
    
@Phira: It seems to be what is meant by the OP, who is aware that the existence of an infinite number of composites in the "Euclid" sequence is an open problem. –  André Nicolas Nov 23 '11 at 23:32
show 1 more comment

Given any prime $p$, there are infinitely many such numbers divisible by $p$.

Here is why: consider $q_1q_2$ where both are primes. Then we want to find $q_1$, $q_2$ such that $q_1q_2+1\equiv 0\pmod{p}$. There are many choices of $ab$ such that $ab\equiv -1 \pmod{p}$, such as $a=1,\ b=p-1$. For any such choice, we then have infinitely many primes $q_1\equiv a \pmod{p}$ and infinitely many primes $q_2\equiv b \pmod{p}$ by Dirichlet's theorem. Hence, we have infinitely many solutions.

It is not hard to see that you can extend this same proof to $p_{k_1}\cdots p_{k_n}$; that is, products of length $n$.

share|improve this answer
    
Apologies I had to change the question. –  Arjang Nov 23 '11 at 12:21
    
@Arjang: And my answer still applies and solves it completely... –  Eric Naslund Nov 23 '11 at 12:47
    
lol overkill dirichlet, see my answer for how Euclid would have solved it –  user1708 Nov 23 '11 at 12:55
1  
@howdy: But your answer is wrong....Andre Nicolas provides a Euclid like proof. –  Eric Naslund Nov 23 '11 at 13:56
add comment

Yes, since any such number is even for any choice of $k_i\geq 2$ (since all primes after $p_1=2$ are odd).

share|improve this answer
    
André Nicolas seems to claim its an open problem though ( math.stackexchange.com/q/54680/3123 ) –  Listing Nov 23 '11 at 10:28
2  
@Listing: That is specifically for the numbers $$p_1p_2\cdots p_n+1,$$ which are all odd since $p_1=2$ is in there. In contrast, Arjang's question is about any choice of primes. –  Zev Chonoles Nov 23 '11 at 10:29
2  
I see then the question indeed doesn't make much sense :-) –  Listing Nov 23 '11 at 10:30
2  
@Arjang: your question is much more interesting if you always include $p_1=2$ in your prime product. Otherwise, since "odd plus one is even"... –  J. M. Nov 23 '11 at 11:43
2  
Okay, who downvoted this? It was addressing an older version of the question... –  J. M. Nov 23 '11 at 12:55
show 3 more comments

If not then there is an M such that if $n = 2 p_{k_1}p_{k_2} \dots p_{k_n} + 1>M$, then n is prime. So if q is an odd composite above M, then q-1 cant be of the form $2 p_{k_1}p_{k_2} \dots p_{k_n}$, but q-1=2t for some t, so then t must be 1 and $M<q=3$, but there is more then one odd composite above $M=2$.

share|improve this answer
2  
A few problems. One is that I believe the OP wants $p_{k_1},\dots, p_{k_n}$ to be distinct, since otherwise the statement, as you have pointed out, is somewhat pointless. Also, what if $n$, the number of primes used, is fixed? –  Eric Naslund Nov 23 '11 at 13:54
    
-1: as pointed out by Eric Naslund, this argument doesn't show that t has to be squarefree. –  lewist Nov 24 '11 at 18:38
add comment

Your Answer

 
discard

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.