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
    Do you know if such an elementary proof exists or you just think there is? Or wished...2011-07-21
  • 21
    Applying your fact to even $n$ shows that the largest prime no greater than $n$ is larger than $n/2$. In other words, proving the fact is as hard as proving Bertrand's postulate.2011-07-21
  • 6
    @ccc, why not post that as an answer?2011-07-21
  • 1
    Related: http://math.stackexchange.com/questions/31973/n-is-never-a-perfect-square-if-n-geq2-is-there-a-proof-of-this-that-doesnt2011-07-21
  • 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