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

I want to prove that:

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

-

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}$.

-
I don't understand ($\Rightarrow$)? –  misi10 Dec 1 '12 at 20:16
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$$