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.

  • $\begingroup$ Let $N=n-2$. Letting $n=3,4,\ldots$ you have your result. $\endgroup$ – 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)$

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


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.