Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

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

3 Answers 3

up vote 1 down vote accepted

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$.

share|improve this answer

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)$

share|improve this answer
    
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.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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