2-adic valuation of $n!$

For discussing Olympiad Level Number Theory problems
mutasimmim
Posts:107
Joined:Sun Dec 12, 2010 10:46 am
2-adic valuation of $n!$

Unread post by mutasimmim » Wed Oct 01, 2014 10:35 am

Prove that $2^n$ never divide $n!$ for any natural number $n$.

User avatar
SANZEED
Posts:550
Joined:Wed Dec 28, 2011 6:45 pm
Location:Mymensingh, Bangladesh

Re: 2-adic valuation of $n!$

Unread post by SANZEED » Wed Oct 01, 2014 12:11 pm

Let $j(n,p)$ denote the highest power of $p$ that divides $n!$. Then, it is a well-known fact that,
$j(n,2)=\displaystyle\sum_{k=1}^{\infty}\lfloor \frac{n}{2^{k}}\rfloor=\lfloor \frac{n}{2}\rfloor+\lfloor \frac{n}{4}\rfloor+\lfloor \frac{n}{8}\rfloor+...$. Now, it is also well-known that $1=\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{8}+...$. So,
$n=\dfrac{n}{2}+\dfrac{n}{4}+\dfrac{n}{8}+...>\displaystyle\lfloor \frac{n}{2}\rfloor+\lfloor \frac{n}{4}\rfloor+\lfloor \frac{n}{8}\rfloor+...$ since $\displaystyle\lfloor x\rfloor \leq x \forall x\in \mathbb{R}$ and $\displaystyle\lfloor \frac{n}{2^{i}}\rfloor$ will eventually become $0$, while $\dfrac{n}{2^{i}}$ won't. So, $n>j(n,2)$ and this is what we require.
$\color{blue}{\textit{To}} \color{red}{\textit{ problems }} \color{blue}{\textit{I am encountering with-}} \color{green}{\textit{AVADA KEDAVRA!}}$

mutasimmim
Posts:107
Joined:Sun Dec 12, 2010 10:46 am

Re: 2-adic valuation of $n!$

Unread post by mutasimmim » Wed Oct 01, 2014 12:54 pm

In case someone is interested, we can atmost have $2^{n-1}\mid n!$, and this value is achieved iff $n$ is a power of $2$.

Post Reply