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 want to prove that:

$2^{n-1}\mid n!$ if and only if $n$ is a power of $2$.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

write out n! and consider how many times each divides by 2 for example 16:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 = 16!
  ^   ^   ^   ^   ^     ^     ^     ^    divisible by 2
      ^       ^         ^           ^    divisible by 2^2
              ^                     ^    divisible by 2^3
                                    ^    divisible by 2^4

so there are $16/2 = 8$ numbers there divisible by 2. $16/4 = 4$ numbers there divisible by 2^2. etc.

in total then, there are 16/2 + 16/2^2 + 16/2^3 + 16/2^4.

In general if 2^r is the highest power of 2 dividing n! then $r = \sum_{i=1} [n/2^i]$.


To show that $2^{n-1}\mid n!$ we thus want to prove $n-1 = \sum_{i=1} [n/2^i]$ iff $n = 2^k$. ($\Leftarrow$) is immediate from computation. For ($\Rightarrow$) Let $2^{k-1} < n < 2^k$ but then $r < n - 1$ by comparing each term of the summation for $n$ and the one for $2^{k}$.

share|improve this answer
    
I don't understand ($\Rightarrow$)? –  misi10 Dec 1 '12 at 20:16
add comment

Hint: It is well-known(?) that the maximal $k$ with $p^k|n!$ is given by $$k=\left\lfloor \frac{n}{p}\right\rfloor+\left\lfloor \frac{n}{p^2}\right\rfloor+\left\lfloor \frac{n}{p^3}\right\rfloor+\ldots$$

share|improve this answer
    
this formula is unknown for me? and then? –  misi10 Nov 30 '12 at 15:44
    
This is sometimes known as De Polignac's formula but is also attributed to Legendre. –  lhf Nov 30 '12 at 16:02
    
i can not continue,give me more hint. –  misi10 Nov 30 '12 at 18:47
1  
Hagen, math.stackexchange.com/questions/141196/… and many other MSE questions. –  Will Jagy Nov 30 '12 at 19:56
1  
There is also some recent thing for posting fixed, easily searchable quality answers to questions, or parts of questions, that come up over and over and over again. I re-posted my little induction proof there but i do not recall how to find it. Certainly, if some fact is necessary for 100 different questions (this probably qualifies), a post with a few correct proofs seems worthwhile. –  Will Jagy Nov 30 '12 at 20:05
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.