10
$\begingroup$

I am trying to wrap my brain around a proof that proves that there are arbitrarily large gaps between successive primes. The proof is

Given a natural number $N\ge2$, consider the sequence of $N$ consecutive numbers $(N+1)!+2$, $(N+1)!+3$, $\dots$, $(N+1)!+ N + 1$. Note that $2$ divides $(N+1)!$ since $2$ is one of the factors in the product that defines $(N+1)!$. So $2$ divides $(N+1)!+2$ hence $(N+1)!+2$ is composite. Similarly, 3 divides $(N+1)!+3$ and so $(N+1)!+3$ is composite as well. Analogously, all the $N$ consecutive numbers from $(N+1)!+2$ to $(N+1)! + N + 1$ are composite. Since the number $N$ is arbitrary, there are strings of consecutive composite numbers of any given length. Hence there are arbitrarily large gaps between successive primes.

What I don't understand is where the function $(N+1)! + N+1$ comes from. How does this relate to the gaps in prime numbers?

$\endgroup$
1
  • 5
    $\begingroup$ Fun fact: this argument actually gives $N+1$ consecutive composites. For if $N+2$ is prime then $(N+1)!+1$ is composite by Wilson's theorem, while if $N+2$ is composite then it has a proper factor which is also a factor of $(N+1)!+N+2$. $\endgroup$
    – David
    Jan 8, 2015 at 1:52

2 Answers 2

Reset to default
6
$\begingroup$

I think your confusion would be cleared up by looking at an actual, concrete example.

Let's say you want a gap of at least ten composite numbers between two primes. If you don't care about finding the very first such gap, you can find a gap with that property by computing $(N + 1)!$. Since in this example we're setting $N = 10$, this gives us $11! = 2 \times 3 \times 4 \times \ldots \times 11 = 39916800$. Verify that:

  • $11! + 2 = 2 \times 149 \times 133949$
  • $11! + 3 = 3 \times 13305601$
  • $11! + 4 = 2^2 \times 59 \times 79 \times 2141$
  • and so on and so forth to
  • $11 + 11 = 11^2 \times 329891$

Notice how the primes between the $+$ and $=$ signs are repeated to the right of the $=$ sign.

Actually, $11! + 12$ is also composite, but we already have our ten consecutive composite numbers.

Now, if you've memorized the first 25 primes or so, you should be able to instantly think of a run of ten consecutive composite numbers without needing to compute anything.

But what if instead I ask you for a run of a hundred consecutive composite numbers? You could laboriously search for the first such run. Or you could just go to $101! + 2$ and have it guaranteed that's composite as well as all the numbers up to $101! + 102$.

$\endgroup$
3
  • $\begingroup$ Wow that's an awesome proof! The only thing I noticed is in the last example shouldn't it be 101! + 101 instead of 101! + 102? $\endgroup$
    – User1
    Jan 8, 2015 at 15:38
  • $\begingroup$ Remember that $n!$ is even for all $n > 1$, and that there is only one even prime, 2. So you could think of $101! + 102$ as a "bonus" composite number. $\endgroup$
    – Robert Soupe
    Jan 8, 2015 at 23:02
  • $\begingroup$ Ok that's cool! $\endgroup$
    – User1
    Jan 8, 2015 at 23:04
1
$\begingroup$

It's chosen especially so the length of consecutive non-primes is at least N.

$\endgroup$
3
  • $\begingroup$ So does N represent the number of numbers between primes? $\endgroup$
    – User1
    Jan 8, 2015 at 1:08
  • 1
    $\begingroup$ Yes. For a fixed $N$, you're trying to find a gap of at least $N$ consecutive numbers, all of which are prime. To do this, you need to cleverly choose a first number $a$, and then prove that $a, a+1, \ldots, a + N-1$ are all composite. Our clever choice is $a = (N-1)! + 2$. This choice doesn't arise naturally from the problem, like in many beginning number theory proofs - it's a something of a trick. $\endgroup$
    – Jair Taylor
    Jan 8, 2015 at 1:20
  • $\begingroup$ Yes. Intuitively $k!$ has a lot of small factors, and so by perturbing it by a small amount you will "catch" at least one of them. For the argument to catch $N$ of them in a row, you need to start at $(N+1)!+2$, and after counting off $N$ numbers which are not prime, you're at the number you asked about. $\endgroup$
    – Eric Stucky
    Jan 8, 2015 at 1:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .