3
$\begingroup$

Find the smallest value of $n$ so that the greater potency of $5$ which divides $n!$ is $5^{84}$. What are the other numbers that enjoy this property?

I thought I would put together an equation of the type $$E_5(n!)=84\\84=\left[\frac{n}{5} \right]+\left[\frac{n}{5^2} \right]+\left[\frac{n}{5^3} \right]+\;...$$ Only I do not see how to proceed, or if this path will take me where I want, someone could help me?

$\endgroup$
5
$\begingroup$

You have

$$E_p(n!) = \sum_{k=1}^\infty \left\lfloor \frac{n}{p^k}\right\rfloor < \sum_{k=1}^\infty \frac{n}{p^k} = \frac{n}{p} \sum_{r=0}^\infty \frac{1}{p^r} = \frac{n}{p}\frac{1}{1-\frac1p} = \frac{n}{p-1},$$

and the difference is small(ish). The first sum is actually finite, all terms for $k > \frac{\log n}{\log p}$ are $0$, writing it as an infinite sum is just convenient.

So to have $E_p(n!) = m$, a ball-park estimate is $n \approx (p-1)\cdot m$, and we must have $n > (p-1)\cdot m$. For $p=5$ and $m = 84$, that yields $n \approx 4\cdot 84 = 336$.

The smallest $n$ will of course be a multiple of $5$, so let's check $n = 340$:

$$E_5(340!) = 68 + 13 + 2 = 83,$$

which is a little too small, we need one more power, so $n = 345$ is it.

$\endgroup$
  • $\begingroup$ For the first sum $k$ goes to infinity?$$$$I do not understand why the summations. $\endgroup$ – marcelolpjunior Nov 20 '13 at 12:47
  • $\begingroup$ Since you take the floor, all terms become $0$ when $p^k > n$, we could write finite bounds, $$\sum_{k=1}^{\left\lfloor \frac{\log n}{\log p}\right\rfloor} \left\lfloor \frac{n}{p^k}\right\rfloor,$$ that would be the same result. Writing an upper bound of $\infty$ is just simpler. $\endgroup$ – Daniel Fischer Nov 20 '13 at 12:54
  • $\begingroup$ Ah, interesting, I did this because it can be infinite. However, because $$\sum_{k=1}^\infty \frac{n}{p^k} = \frac{n}{p-1}?$$ $\endgroup$ – marcelolpjunior Nov 20 '13 at 12:59
  • $\begingroup$ Geometric series. Just added one more step to show it. $\endgroup$ – Daniel Fischer Nov 20 '13 at 13:02
  • 1
    $\begingroup$ If $n$ is a multiple of $5$, the highest power of $5$ dividing $n!$ is greater than the highest power of $5$ dividing $(n-1)!$. If $n$ is not a multiple of $5$, the highest power of $5$ dividing $n!$ is also the highest power of $5$ dividing $(n-1)!$. So if $345$ is the smallest $n$ with $5^{84}$ dividing $n!$ but $5^{85}$ not dividing $n!$, the other numbers with this property are - can you figure it out from the above? $\endgroup$ – Daniel Fischer Nov 21 '13 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.