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

1 Answer
Oct 4, 2016

Answer:

#n=8075#

Explanation:

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.