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
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.
No comments:
Post a Comment