5
$\begingroup$

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.

4 Answers 4

8

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.

  • 0
    This is probably the best answer for the OP.2011-11-23
  • 0
    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.2011-11-23
  • 0
    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.2011-11-23
  • 0
    @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.2011-11-23
  • 0
    @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.2011-11-23
  • 0
    @AndréNicolas Ok, thanks.2011-11-23
6

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$.

  • 0
    Apologies I had to change the question.2011-11-23
  • 0
    @Arjang: And my answer still applies and solves it completely...2011-11-23
  • 0
    lol overkill dirichlet, see my answer for how Euclid would have solved it2011-11-23
  • 1
    @howdy: But your answer is wrong....Andre Nicolas provides a Euclid like proof.2011-11-23
1

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

  • 0
    André Nicolas seems to claim its an open problem though ( http://math.stackexchange.com/q/54680/3123 )2011-11-23
  • 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.2011-11-23
  • 2
    I see then the question indeed doesn't make much sense :-)2011-11-23
  • 0
    @Listing : Updated the question2011-11-23
  • 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"...2011-11-23
  • 0
    @J.M. : Damn, I missed that, modified it. In Euler counter example that product of consecutive primes +1 at times was composite, 2 · 3 · 5 · 7 · 11 · 13 + 1 = 30,031 = 59 · 509 I wondered if there are infinitely many composites.2011-11-23
  • 0
    Apologies I had to change the question.2011-11-23
  • 2
    Okay, who downvoted this? It was addressing an older version of the question...2011-11-23
0

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, but there is more then one odd composite above $M=2$.

  • 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?2011-11-23
  • 0
    -1: as pointed out by Eric Naslund, this argument doesn't show that t has to be squarefree.2011-11-24