For $n\geq 6$, the smallest composite number that is not a factor of $n!$ is $2p$, where $p$ is the smallest prime bigger than $n$?

Question

I'm pretty sure the following statement is true:

For $n\geq 6$, the smallest composite number that is not a factor of $n!$ is $2p$, where $p$ is the smallest prime bigger than $n$.

But I'm having trouble proving it.

Here is an attempt by induction. The property is true when $n=6$, and assume it's true for $n$. If $n+1$ isn't prime, the induction step is trivial, for the smallest prime bigger than $n+1$ is equal to the smallest prime bigger than $n$; call this prime $p$. But by hypothesis all composites smaller than $2p$ divide $n!$, hence $(n+1)!$.

The harder case is when $n+1$ is prime. Let $q$ denote the next prime, i.e. the smallest prime bigger than $n+1$. We know by hypothesis that all composites smaller than $2(n+1)$ divide $n!$, hence $(n+1)!$. We also know $2(n+1)$ divides $(n+1)!$. To finish, we need to show that all composites $m$ strictly between $2(n+1)$ and $2q$ divide $(n+1)!$.

This is where I get stuck. It certainly helps that the ratio $\frac{q}{n+1}$ can't be larger than 2 (by Bertrand's postulate; I imagine the bound can be sharpened but I know embarrassingly little number theory). It's also obvious that the prime factors of any such composite $m$ are all smaller than $q$. What I don't quite see is an argument to ensure the powers of those prime factors aren't too large.

Feel free to give alternative approaches, rather than by induction, if there is a much simpler proof I've overlooked.

Answer 1

A composite $m$ with $2(n+1)\lt m \lt 2q$ cannot be twice a prime because $q$ is the next prime after $n+1$, so must be able to be factored into $ab$ with $a,b \lt n+1$. Then $a,b$ are separately factors of $(n+1)!$ and $ab$ divides $(n+1)!$ unless $a=b$. We will have $a^2$ divide $(n+1)!$ unless $a \gt \frac {n+1}2$ because $a,2a$ are both factors. But then $a^2 \gt \frac {(n+1)^2}4 \ge 4(n+1) \ge 2q$ as long as $n \ge 15$ by Bertrand's postulate. We can check the cases up to $15$ by hand to complete the proof.

Answer 2

In my opinion, induction is not always the best way to prove everything.

For this problem, I would first review the basic definition of the factorial: $$n! = \prod_{i = 1}^n i.$$ This means that $n!$ is divisible by every prime less than $n$, e.g., $6!$ is divisible by $2, 3, 5$ but not by $7$. Now, $8 \mid 6!$, as also do $9, 10, 12$.

That's because they're composite numbers divisible by some combination of the primes that divide $6!$ but without excess multiplicity, e.g., $8 = 2 \times 4$, $9 \mid 3 \times 6$, $10 = 2 \times 5$, $12 = 3 \times 4$.

Obviously $p \nmid n!$ if $p$ is the smallest prime greater than $n$. But $p$ is prime, not composite. If there are composite numbers between $n$ and $p$, it seems obvious to me that they must be divisible by some prime less than $p$.

Answer 3

HINT: What I would do first is ask why it's not true for $n < 6$. As in the other answers, $p$ is the smallest prime greater than $n$.

• It actually is true for $n = 1$.
• For $n = 2$, the composite we're looking for is 4, which is $2n$ rather than $2p$.
• For $n = 3$, it turns out that the answer is also 4.
• For $n = 4$, the composite we're looking for is 9, the square of 3. The problem here is that 4! doesn't have the desired multiplicity of the factor 3.
• And for $n = 5$, the answer is also 9.

What's going on with most $n < 6$ is that although $2p \nmid n!$, there is a smaller composite number, the square of a prime, which does not divide $n!$.

For $n = 6$ and beyond, the squares of primes don't worry us as much because smaller multiples of those primes give $n!$ sufficient multiplicity of those primes.

As Dave already said, each composite between $n$ and $p$ must be divisible by some prime less than $n$. This is also true of the composites between $p$ and $2p$. They can't be divisible by any larger primes.

So the whole problem boils down to the multiplicity of the primes less than or equal to $n$. There's still a long ways to go from here, but it can be accomplished by elementary means only.