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

  • 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).

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

  • 0
    -1: as pointed out by Eric Naslund, this argument doesn't show that t has to be squarefree.2011-11-24