Let v_p(k)vp(k) be the multiplicity of pp as a factor of kk. That is, v_p(k)vp(k) is the greatest integer such that p^(v_p(k))|kpvp(k)∣k.
Observations:
-
For any k in ZZ^+ 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 ZZ^+, we have j|k <=> v_p(j) <= v_p(k) 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^2016xx5^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(i). 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(5^1) = 1
v_5(5^2) = 6
v_5(5^3) = 31
v_5(5^4) = 156
v_5(5^5) = 781
As 2016 = 2(781)+2(156)+4(31)+3(6), 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(5^5)+2(5^4)+4(5^3)+3(5^2) = 8075
A computer can quickly verify that sum_(i=1)^(8075)v_5(i)=2016. Thus 10^2016 | 8075!, and as 5|8075! with multiplicity 2016 and 5|8075, it is clear that no lesser value will suffice.
