4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user139000 Oct 27 '14 at 15:20
  • 1
    $\begingroup$ You should modify the title, because the smallest number $n$ such that $5^{84}$ divides it, is, of course, $5^{84}$... $\endgroup$ – ajotatxe Oct 27 '14 at 15:23
2
$\begingroup$

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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mark Bennet Oct 27 '14 at 15:47
3
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.