1
$\begingroup$

Why is it that if I multiply a certain number of consecutive primes starting from $2$ and add $1$, I get another prime?

This property is used it prove that there are infinitly many primes, but why is it correct?

$\endgroup$
  • 2
    $\begingroup$ $$2⋅3⋅5⋅7⋅11⋅13+1=59\cdot509$$ $\endgroup$ – Did Sep 25 '16 at 7:36
  • 1
    $\begingroup$ You don't necessarily get another prime, but you do get a number whose prime factors are neither ones of those which you have used in your product. Hence there are infinitely many primes. $\endgroup$ – barak manos Sep 25 '16 at 7:47
  • $\begingroup$ This is what happens when you're satisfied by a few small examples, Daniel. It's no accident that @Did gave you 13 as a counterexample, it's the smallest counterexample. The next example is 31, and the next after that is 379. See oeis.org/A005234 $\endgroup$ – Robert Soupe Sep 25 '16 at 17:09
  • $\begingroup$ See also oeis.org/A051342 $\endgroup$ – Robert Soupe Sep 25 '16 at 17:11
3
$\begingroup$

That's not exactly what it's doing. It's not saying that (the product of the first $n$ primes)$+1$ is prime, it's saying that it has a prime factor that is not an element of the first $n$ primes. The classical proof (or a suitable variation) goes like this:

Assume for the sake of contradiction that there are only finitely many primes $p_1,p_2,...,p_n$. Then consider the number

$$X = p_1p_2p_3...p_n+1$$

We know $X$ must have a prime factorization, so there exists some prime $q|X$. We know that, since these $p_i$ are the only primes, it must be $p_k$ for some $k\leq n$. Thus,

$$ap_k=X$$

for some integer $a$. However,

$$bp_k=X-1$$

for some integer $b$, because of how $X$ is defined. Thus

$$1 = X-(X-1) = (a-b)p_k$$

so $p_k|1$, a contradiction. This finishes the proof.

We never state that $X$ is prime, just that it must have a prime divisor that is not in our original list.

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.