8
$\begingroup$

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.

$\endgroup$

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Ah, that's nice; thanks. You do use Bertrand there at the end, with $4(n+1)\geq 2q$. $\endgroup$ Jun 30, 2017 at 20:19
  • $\begingroup$ @symplectomorphic: that is right. Without that we could have the problem that $5^2=25$ does not divide $9!$ even though $5$ does and the next prime higher could be $13$. Here $11$ saves us. As $n$ gets larger, this square goes up as $n^2$ so it gets too big to be a problem. $\endgroup$ Jun 30, 2017 at 20:35
  • $\begingroup$ Why do you work with $n+1$? You are not doing induction after all $\endgroup$ Jun 30, 2017 at 20:46
  • $\begingroup$ @HagenvonEitzen: I was following up on the OPs post where he was inducting, assuming that the smallest composite greater than $n!$ was twice the next prime above $n$ and wanting to prove it true for $n+1$. OP remarked that it was obviously true when $n$ is not a prime, but having trouble when $n+1$ is prime. I think you could also prove it as above for all primes and say it then stays true up to the next prime. $\endgroup$ Jun 30, 2017 at 21:11
2
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Your last sentence is obviously true, but it does not suffice to prove the theorem; it does not even suffice to show that any composite number between $n$ and $p$ must divide $n!$. (Just because a composite number is divisible by a prime less than $p$ does not mean it divides $n!$. Take $n=3$ to see this.) What needs to be shown is that any composite number smaller than $\color{red}{2p}$ divides $n!$ (where $n$ and $p$ are as you've defined them). $\endgroup$ Jun 30, 2017 at 22:32
  • $\begingroup$ @symplectomorphic I think you should post an answer. I think that David meant to post a hint but didn't declare it as such. $\endgroup$ Jul 1, 2017 at 16:29
  • $\begingroup$ @Robert Soupe: I asked the question. David's post isn't a hint; there's nothing in it that helps resolve the step where I was stuck. $\endgroup$ Jul 1, 2017 at 16:36
  • $\begingroup$ @symplectomorphic Oops, sorry, I neglected to check that detail. $\endgroup$ Jul 1, 2017 at 17:27
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ "So the whole problem boils down to the multiciplicity of primes less than or equal to $n$." This does not answer the question or provide a hint. I said as much explicitly in the statement of the question: "What I don't quite see is an argument to ensure the powers of those primes aren't too large." I already showed what the problem boiled down to: the question was how to proceed from there. $\endgroup$ Jul 1, 2017 at 18:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .