# Deduce that there is a prime gap of length $\geq n$ for each $n \in \mathbb{N}$

Show that for any $n \in \mathbb{N}$, the numbers $n! + i$, for $2 \leq i \leq n$, are all composite. Deduce that there is a prime gap of length $\geq n$ for each $n \in \mathbb{N}$.

I have done the first bit. I'm a little confused at the second bit. I said:

We know that $k \mid n!$ for some $k \in \mathbb{N}$ with $2 \leq k \leq n$ and so $k \mid n! + k$, which tells us that $n! + k$ is composite for $2 \leq k \leq n$. So if we set $p$ to be the largest prime $< n! + 2$ and $q$ the smallest prime $> n! + n$, then subtracting these two should give us our answer. S0 we get

$$q - p \geq n! + n - n! - 2 = n - 2.$$

Where have I gone wrong?

EDIT: A second question I have is

Show that is $2^n - 1$ is prime then $n$ is prime.

In the answers it starts of by doing an expansion like

$$2^n -1 = (2 - 1)(1 + 2 + 2^2 + \cdots + 2^{n-1}).$$

Where does this expansion come from?

EDIT 2: Ok, so I get the expansion then. In the proof, it says, assume $n = ab$ is not prime for some $a,b > 1$. Then

$$(2^a)^b - 1 = (2^a - 1)(1 + 2^a + (2^a)^2 + \cdots (2^a)^{b-1})$$

which clearly is not prime and so $2^n - 1$ is not prime if $n$ is not prime. So how does this prove $2^n - 1$ is prime when $n$ is prime? Surely you can't just assume that the top bit shows all the different ways of writing composite numbers and so we would still need to prove someway for $2^n - 1$ being prime if $n$ is prime.

• Let $N=n-2$. Letting $n=3,4,\ldots$ you have your result. – Jared Apr 12 '13 at 18:07

While the other answers point out the valuable strategy of being adaptable, they kind of miss the point here: since $q > n!+n$ and $q$ is an integer, $q \ge n!+n+1$ (how could it be any smaller?). By a similar argument, $p \le n!+1$, so $q-p \ge n$. You have already found a gap of size $n$.

You showed that for each $n$, there's a gap of size $n-2$. In particular, for $n+2$, there's a gap of size $(n+2)-2 = n$.

For your second question, it's an easy algebraic identity:

$x^n - 1 = (x-1)(x^{n-1} + x^{n-2} + \ldots + x + 1)$

• Is it necessary to say "it's a high school..."? I didn't learn that in high school, IIRC. – Pedro Tamaroff Apr 12 '13 at 18:17
• @xyzzyz Ok, thanks for that. I have put another edit, if you don't mind looking at it. – Kaish Apr 12 '13 at 18:24
• Actually, I'll make a new thread as I have another question – Kaish Apr 12 '13 at 18:35

Just choose $p$ to be largest prime $<(n+2)!+2$ and $q$ the smallest prime $>(n+2)!+(n+2)$ , then $$q-p \geq (n+2)!+(n+2)-(n+2)!-2 = n.$$