\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

Let $p$ be a prime number and suppose that $n!=p^es$ with
HCT$(p,s)=1$ where $n!$ is the product of the integers
$1,2,\ldots,n$, as usual.

\begin{description}

\item[(i)]
Show that

$$e=\left[\frac{n}{p}\right]+\left[\frac{n}{p^2}\right]+\left[\frac{n}{p^3}\right]+\ldots+\left[\frac{n}{p^r}\right]+\ldots$$

where $[x]$ denotes the greatest integer less than of equal to
$x$.

\item[(ii)]
If $n=a_0+a_1p+a_2p^2+\ldots+a_kp^k$, where $0\leq a_i\leq p-1$
for each $i$, prove that $e$ in part (i) is given by

$$e=(p-1)^{-1}(n-a_0-a_1-a_2-\ldots-a_k).$$

\item[(iii)]
Show that the largest power of 2 which will divide the binomial
coefficient

$$\left(\begin{array}{c}2^t\\2^{t-1}-2\end{array}\right)$$

is $2^{t-1}$, if $t\geq3$.

\end{description}



ANSWER

\begin{description}

\item[(i)]
Consider the numbers $1,2,\ldots,n$. Their product is $n!$. We can
calculate $e$ by taking each of these numbers, finding the exact
power of $p$ which divides it and then $e$ is the sum of all these
exponents. However, we are going to calculate this sum another
way. Consider th following array:

$$\begin{array}{ccccc}p,&2p,&3p,&\ldots&\left[\frac{n}{p}\right]p,\\
p^2,&2p^2,&3p^2,&\ldots&\left[\frac{n}{p^2}\right]p^2,\\
p^3,&2p^3,&3p^3,&\ldots&\left[\frac{n}{p^3}\right]p^3,\\
\vdots&\vdots\\
p^k,&2p^k,&3p^k,&\ldots&\left[\frac{n}{p^k}\right]p^k\\
\vdots&\vdots\end{array}$$

The first row consists of all multiples of $p$ less than or equal
to $n$. The second row is all the multiples of $p^2$ less than or
equal to $n$ and so on. A number which is less than or equal to
$n$ and is exactly divisible by $p^s$ will appear exactly $s$
times in the array- once on each of the first $s$ rows. Hence the
number of numbers in this array is exactly the sum of the
exponents mentioned at the start of the proof. Clearly this number
is equal to $\left[\frac{n}{p}\right]+ \left[\frac{n}{p^2}\right]+
\left[\frac{n}{p^3}\right] +\ldots+ \left[\frac{n}{p^r}\right]
+\ldots$ as required.

\item[(ii)]
We have

\begin{eqnarray*}
\left[\frac{n}{p}\right]&=&a_1+a_2p+\ldots+a_kp^{k-1},\\
\left[\frac{n}{p^2}\right]&=&a_2+a_3p+\ldots+a_kp^{k-2},\\
\vdots&\vdots&\vdots\\
\left[\frac{n}{p^{k-1}}\right]&=&a_{k-1}+a_kp,\\
\left[\frac{n}{p^k}\right]&=&a_k.
\end{eqnarray*}

Hence

\begin{eqnarray*}
e&=&a_1+a_2(1+p)+a_3(1+p+p^2)+\ldots+a_k(1+p+\ldots +p^{k-1})\\
&=&(p-1)^{-1}(a_1(p-1)+a_2(p^2-1)+\ldots+a_k(p^k-1))\\
&=&(p-1)^{-1}(n-a_0-a_1-a_2-\ldots-a_k)
\end{eqnarray*}

as required.

\item[(iii)]
If $n\geq3$,

$$\left(\begin{array}{c}2^n\\2^{n-1}-2\end{array}\right)
=\frac{(2^n)!}{(2^{n-1}-2)!(2^{n-1}+2)!}$$

by part (ii)

\begin{eqnarray*}
(2^n)!&=&(2t+1)2^{2^n-1}\\
(2^{n-1}-2)!&=&(2u+1)2^{2^{n-1}-2-(n-2)}\\
(2^{n-1}+2)!&=&(2v+1)2^{2^{n-1}+2-1}
\end{eqnarray*}

Hence the power of 2 exactly dividing this binomial coefficient is
$2^e$ where

$$e=2^n-1-(2^{n-1}-2-(n-2))-(2^{n-1}+2-2)=n-1$$


\end{description}




\end{document}