6
$\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$
  • 3
    $\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 '15 at 1:52
2
$\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$
  • $\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 '15 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 '15 at 23:02
  • $\begingroup$ Ok that's cool! $\endgroup$ – User1 Jan 8 '15 at 23:04
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So does N represent the number of numbers between primes? $\endgroup$ – User1 Jan 8 '15 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 '15 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 '15 at 1:25

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.