Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
Do you know if such an elementary proof exists or you just think there is? Or wished... –  Patrick Da Silva Jul 21 '11 at 7:51
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. –  user83827 Jul 21 '11 at 7:56
6  
@ccc, why not post that as an answer? –  Gerry Myerson Jul 21 '11 at 9:48
1  
Related: math.stackexchange.com/questions/31973/… –  lhf Jul 21 '11 at 11:44
1  
@ccc: Gerry's right; do post an answer. –  J. M. Oct 4 '11 at 23:06
show 3 more comments

1 Answer

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.

share|improve this answer
    
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. –  mixedmath Aug 16 '12 at 7:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.