Let #v_p(k)# be the multiplicity of #p# as a factor of #k#. That is, #v_p(k)# is the greatest integer such that #p^(v_p(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.
