# The smallest number $n$ such that $5^{84}$ divides $n!$.

I am triyng to solve the following exercise:

Find the smallest natural number $n$ such that the biggest power of $5$ which divides $n!$ is $5^{84}$. How many natural numbers there are with this property?

I am trying to solve this exercise by using the following formula:

$E_{5}(n!)=[\dfrac{n}{5}]+[\dfrac{n}{5^{2}}]+[\dfrac{n}{5^{3}}]+\cdots$

but I was not able to find the solutions.

• In order for $5^{84}$ to divide $n!$, the total multiplicity of the prime factor 5 in all numbers from the range $1,...,n$ must be 84. – user139000 Oct 27 '14 at 15:20
• You should modify the title, because the smallest number $n$ such that $5^{84}$ divides it, is, of course, $5^{84}$... – ajotatxe Oct 27 '14 at 15:23

The answer is $345!$, because it has $69$ multiples of $5$, $13$ multiples of $25$ and $2$ multiples of $125$ (and $69+13+2 = 84$).

How to find it : it's obvious that the answer is lower than $84*5 = 420$. I know that around $1/5$ numbers are multiples of $25$ so $420$ is around $6/5$ of an overshot. So I tested $5/6*420 = 350$ and saw that it contained $86$ factors of $5$. Noticing that $350$ itself is a multiple of $5$ and $25$, I only needed to go down the the highest lower multiple of $5$ to get the correct answer.

• How did you find $n=345$? – spohreis Oct 27 '14 at 15:27
• @spohreis : Edited ! – Traklon Oct 27 '14 at 15:31

As $\frac 15+\frac 1{25}+\frac 1{125}\dots=\frac 14$, you expect the answer to be about $4\cdot 84=336$ Start with that $n$ and move up or down as required.

• Start with $340$ because it is clear that if $n$ is not divisible by $5$, $(n-1)!$ is divisible by the same power of $5$ as $n!$ - so you can go up $5$ at a time. – Mark Bennet Oct 27 '14 at 15:47

Note that $$E_5(5!)=1$$ $$E_5(25!)=5\cdot 1+1=6$$ $$E_5(125!)=5\cdot 6+1=31$$ $$E_5(625!)=5\cdot 31+1=156$$

Now that we have overtaken $84$ we go a step back and since $84=31\cdot2+6\cdot 3+1\cdot4$ we make $$125\cdot 2+25\cdot 3+5\cdot 4=250+75+20=345$$ so $E_5(345!)=84$.

For this exercise, it's a good idea to review some basic properties of factorials. If a given prime $p \leq n$, then $p|n!$. Also, the multiples of that prime less than or equal to $n$ contribute to $p$'s exponent in the factorization of $n!$.

Obviously, the smallest factorial that is divisible by $5$ is $5!$. $6!$ is also divisible by $5$, but since $6 = 2 \times 3$, it doesn't contribute to $5$'s exponent. When we get to $10!$, since $10 = 2 \times 5$, the factorization of $10!$ now includes $5^2$. Each further multiple of $5$ adds to the exponent, but you have to take care to add the right number to the exponent: for example, in going from $24!$ to $25!$, be sure to add $2$ to $5$'s exponent. This is what the $E_5(n!)$ formula is getting at.

So, the factorization of $100!$ includes $5^{24}$ because twenty numbers contribute at least $1$ each to $5$'s exponent, and four of them contribute $2$ each (namely, $25, 50, 75, 100$). By the time you get to $300!$, the exponent for $5$ has gotten to $74$. Just keep adding until you find $345! = 2^{340} \times 3^{170} \times 5^{84} \times \ldots$

On to the second part of the exercise. Clearly $346!$ also has this property, as do $347!$, $348!$ and $349!$. But not $350!$, because by multiplying by $350$ you add $2$ to $5$'s exponent.