13. The number $16!\div 2^{k}$ is an odd integer. Note that $n!=1 \times 2 \times 3 \times \cdots \times(n-1) \times n$. What is the value of $k$ ?
A 9
B 11
C 13
D 15
E 17
Solution
D
The number $k$ that we seek is such that $16!=2^{k} \times q$, where $q$ is an odd integer. Thus $k$ is the power of 2 that occurs in the prime factorization of 16 !.

Method 1
To find the highest power of 2 that is a factor of 16 ! we need only consider the even numbers that occur in the product $1 \times 2 \times \cdots \times 15 \times 16$ that gives the value of 16 .

In the following table we give the powers of 2 that divide each of these factors.
\begin{tabular}{lcccccccc}
\hline factor & 2 & 4 & 6 & 8 & 10 & 12 & 14 & 16 \\
power of 2 & 1 & 2 & 1 & 3 & 1 & 2 & 1 & 4 \\
\hline
\end{tabular}

The power of 2 in the prime factorization of 16 ! is the sum of the powers in the second row of this table. That is, it is $1+2+1+3+1+2+1+4=15$.
Hence, the required value of $k$ is 15 .

Method 2
Note:
In this method we use the formula, usually attributed to the French mathematician Adrian-Marie Legendre (1752-1833), for the highest power of a prime $p$ that divides $n!$. This formula makes use of the floor function which we first explain.

We define the floor of $x$, written as $\lfloor x\rfloor$, to be the largest integer that is not larger than $x$.
For example, $\left\lfloor 2 \frac{6}{7}\right\rfloor=2,\lfloor 4.275\rfloor=4,\lfloor\pi\rfloor=3,\lfloor 7\rfloor=7,\lfloor 0.43\rfloor=0$ and $\lfloor-5.23\rfloor=-6$.
According to Legendre's formula, the highest power of the prime $p$ that divides $n$ ! is given by
$$
\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^{2}}\right\rfloor+\left\lfloor\frac{n}{p^{3}}\right\rfloor+\ldots
$$

At first sight, the formula involves an infinite sum. However, if $p^{k}>n$, we have $0<\frac{n}{p^{k}}<1$ and hence $\left\lfloor\frac{n}{p^{k}}\right\rfloor=0$. Therefore only a finite number of terms in the above sum are non-zero. The number of non-zero terms in this sum is the largest integer $k$ for which $p^{k} \leq n$.

By Legendre's formula the highest power of 2 that divides 16 ! is $k$, where
$$
\begin{aligned}
k & =\left\lfloor\frac{16}{2}\right\rfloor+\left\lfloor\frac{16}{2^{2}}\right\rfloor+\left\lfloor\frac{16}{2^{3}}\right\rfloor+\left\lfloor\frac{16}{2^{4}}\right\rfloor \\
& =\left\lfloor\frac{16}{2}\right\rfloor+\left\lfloor\frac{16}{4}\right\rfloor+\left\lfloor\frac{16}{8}\right\rfloor+\left\lfloor\frac{16}{16}\right\rfloor \\
& =\lfloor 8\rfloor+\lfloor 4\rfloor+\lfloor 2\rfloor+\lfloor 1\rfloor \\
& =8+4+2+1 \\
& =15 .
\end{aligned}
$$

For INVESTIGATION
13.1 Why is 15 the only value of $k$ for which $16!\div 2^{k}$ is an odd integer?
13.2 Use Legendre's formula to find the highest power of 3 that divides 16!.
13.3 What is the highest power of 2 that divides 100 !?
13.4 What is the highest power of 3 that divides 100!?
13.5 Find the prime factorization of 100 !
13.6 Find the least positive integer $n$ such that $2^{100}$ is a factor of $n!$.
13.7 Prove that Legendre's formula is correct.
That is, show that the highest power of the prime $p$ that divides $n$ ! is given by the sum
$$
\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^{2}}\right\rfloor+\left\lfloor\frac{n}{p^{3}}\right\rfloor+\cdots+\left\lfloor\frac{n}{p^{k}}\right\rfloor,
$$
where $k$ is the largest integer such that $p^{k} \leq n$.
13.8 Let $p$ be a prime number and let $n$ be a positive integer. Find a formula in terms of $p$ and $n$ for the highest power of $p$ that divides $\left(p^{n}\right)!$.