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
$\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$
  • $\begingroup$ Ah, that's nice; thanks. You do use Bertrand there at the end, with $4(n+1)\geq 2q$. $\endgroup$ – symplectomorphic Jun 30 '17 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$ – Ross Millikan Jun 30 '17 at 20:35
  • $\begingroup$ Why do you work with $n+1$? You are not doing induction after all $\endgroup$ – Hagen von Eitzen Jun 30 '17 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$ – Ross Millikan Jun 30 '17 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$
  • $\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$ – symplectomorphic Jun 30 '17 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$ – Robert Soupe Jul 1 '17 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$ – symplectomorphic Jul 1 '17 at 16:36
  • $\begingroup$ @symplectomorphic Oops, sorry, I neglected to check that detail. $\endgroup$ – Robert Soupe Jul 1 '17 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$
  • $\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$ – symplectomorphic Jul 1 '17 at 18:18

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.