# What is the smallest integer n such that n! = m cdot 10^(2016)?

Oct 4, 2016

$n = 8075$

#### Explanation:

Let ${v}_{p} \left(k\right)$ be the multiplicity of $p$ as a factor of $k$. That is, ${v}_{p} \left(k\right)$ is the greatest integer such that ${p}^{{v}_{p} \left(k\right)} | k$.

Observations:

• For any $k \in {\mathbb{Z}}^{+}$ and $p$ prime, we have v_p(k!) = sum_(i = 1)^k v_p(i)
(This can be easily proven by induction)

• For any integer $k > 1$, we have v_2(k!) > v_5(k!).
(This is intuitive, as multiples of powers of $2$ occur more frequently than multiples of equivalent powers of $5$, and may be proven rigorously using a similar argument)

• For $j , k \in {\mathbb{Z}}^{+}$, we have $j | k \iff {v}_{p} \left(j\right) \le {v}_{p} \left(k\right)$ for any prime divisor $p$ of $j$.

Proceeding, our goal is to find the least integer $n$ such that 10^2016|n!. As ${10}^{2016} = {2}^{2016} \times {5}^{2016}$, then by the third observation, we need only confirm that 2016 <=v_2(n!) and 2016 <= v_5(n!). The second observation means that the latter implies the former. Thus, it is sufficient to find the least integer $n$ such that v_5(n!) = sum_(i=1)^nv_5(i) >= 2016.

To find $n$ we will make an observation which will allow us to calculate v_5(5^k!).

Between $1$ and ${5}^{k}$, there are ${5}^{k} / 5$ multiples of $5$, each of which contribute at least $1$ to the sum ${\sum}_{i = 1}^{{5}^{k}} {v}_{5} \left(i\right)$. There are also ${5}^{k} / 25$ multiples of $25$, each of which contribute an additional $1$ to the sum after the initial count. We can proceed in this manner until we reach a single multiple of ${5}^{k}$ (which is ${5}^{k}$ itself), which has contributed $k$ times to the sum. Calculating the sum in this manner, we have

v_5(5^k!) = sum_(i=1)^(5^k)v_5(i)=sum_(i=1)^(k)5^k/5^i=sum_(i=1)^k5^(k-i)=sum_(i=0)^(k-1)5^i=(5^k-1)/(5-1)

Thus, we find that v_5(5^k!) = (5^k-1)/4

Finally, we will find $n$ such that v_5(n!) = 2016. If we calculate v_5(5^k!) for several values of $k$, we find

${v}_{5} \left({5}^{1}\right) = 1$
${v}_{5} \left({5}^{2}\right) = 6$
${v}_{5} \left({5}^{3}\right) = 31$
${v}_{5} \left({5}^{4}\right) = 156$
${v}_{5} \left({5}^{5}\right) = 781$

As $2016 = 2 \left(781\right) + 2 \left(156\right) + 4 \left(31\right) + 3 \left(6\right)$, $n$ needs two "blocks" of ${5}^{5}$, two of ${5}^{4}$, four of ${5}^{3}$, and three of ${5}^{2}$. Thus, we get

$n = 2 \left({5}^{5}\right) + 2 \left({5}^{4}\right) + 4 \left({5}^{3}\right) + 3 \left({5}^{2}\right) = 8075$

A computer can quickly verify that ${\sum}_{i = 1}^{8075} {v}_{5} \left(i\right) = 2016$. Thus 10^2016 | 8075!, and as 5|8075! with multiplicity $2016$ and $5 | 8075$, it is clear that no lesser value will suffice.