6
$\begingroup$

I need an elementary proof of the fact(that is without using Bertrand's Postulate or something like that): Let $p(n)$ be the largest prime not greater than $n$. Then $p(n)$ will come exactly once in the factorization of $n!$.

Corollary: $n!$ is not a perfect power.

  • 1
    @ccc: Gerry's right; do post an answer.2011-10-04

1 Answers 1

7

This is a fleshing out of ccc's comment above:

Claim: The statement If $n \geq 3$, then the largest prime $p_n$ less than or equal to $n$ will divide $n!$ exactly once is equivalent to Bertrand's Postulate, saying there is always a prime between $n$ and $2n$ for $n \geq 2$.

$(\impliedby)$
Assuming Bertrand's Postulate, there is a prime between $n$ and $n/2$, and the largest prime less than or equal to $n$ will thus also be between $n$ and $n/2$. But then this prime will divide $n!$ exactly once (the second factor would come from $2p_n$, requiring $2p_n < n$). $\diamondsuit$

$(\implies)$
Assuming the statement in the OP, then we apply this statement to the number $2n$. Then the fact that the largest prime $p_{2n}$ less than $2n$ will divide $2n!$ exactly once is equivalent to the fact that $p_{2n}$ is greater than $2n/2 = n$ (again, the second factor would come from $2p_{2n}$). $\diamondsuit$

Thus proving the statement in the OP is exactly as hard as probing Bertrand's Postulate.

  • 0
    Yes indeed. I happen to be talking about Bertrand's Postulate and this question today with a high schooler very interested in number theory today, which made me think of this question.2012-08-16