8
$\begingroup$

I was checking this number theory exercise:

Consider the numbers

$2 + 1, 2 · 3 + 1, 2 · 3 · 5 + 1, 2 · 3 · 5 · 7 + 1, · · · $

Show, by computing several values, that there are composite numbers in this sequence. (This shows that in the proof of Euclid’s theorem, these numbers are not necessarily prime, so it is necessary to look at prime factors of these numbers.)

Is there a way to show that all numbers are not necessarily prime by a different way than computing several values?

$\endgroup$
  • $\begingroup$ I would be very surprised if this would be possible. I see no reason that those numbers could not be all prime. $\endgroup$ – Peter Sep 9 '18 at 21:29
4
$\begingroup$

This is not an answer, just an intuition. Certainly not a rigorous proof.

Let's take the time to formalize your notation and terminology. $p_i$ gives us the $i$th prime, starting with $p_1 = 2$, going on to 3 and all the odd primes. Then $n$ primorial is $$n\# = \prod_{i = 1}^n p_i$$ and the $n$th "Euclid number" is $1 + n\#$.

So the numbers you're considering are listed in Sloane's http://oeis.org/A006862 2, 3, 7, 31, 211, 2311, 30031, 510511, 9699691, 223092871, 6469693231, 200560490131, etc. (they regard $p_0 = 1$, that's convenient sometimes).

Note that $\sqrt 3 < 2$, and $2 < \sqrt 7 < 3$. But already with 31 we have $\sqrt{31} > 5$ by a slight margin. And clearly $\sqrt{211} > 7$ by about that much.

Then, as $n$ gets larger, the gulf between $p_n$ and $\sqrt{1 + n\#}$ widens. By the prime number theorem, you know there are something like $$\frac{\sqrt{n\#}}{\log \sqrt{n\#}} - \frac{p_n}{\log p_n}$$ primes between $p_n$ and $\sqrt{n\#}$.

Obviously $1 + n\#$ is not divisible by any prime between 2 and $p_n$. Here's the intuition part: can it always be the case that none of the primes between $p_n$ and $\sqrt{n\#}$ divide $1 + n\#$?

$\endgroup$
  • 2
    $\begingroup$ Another OEIS sequence that might be relevant: oeis.org/A051342 e.g., $13 < 59 < \sqrt{30031}$. $\endgroup$ – Lisa Sep 15 '18 at 20:17

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.