What is the largest integer value of $n$ for which $8^n$ evenly divides $(100!)$?

Question

I know that this may be an unnecessary question, but I am a bit confused. The problem asks for the highest integer $n$ such that $8$ to the power of $n$ is divisible, evenly of course, by $100$. Now, I searched the site, and, in general, it seems that one can use floor function for a problem like this, but this seems to only work for prime numbers possibly. My process, which I realized was incorrect:

The floor function of $100/8 = 12$, and then doing it for the second power would lead to one, and, by adding those up, I acquired thirteen. Of course, after seeing the answer, $32$, I went back to see what was wrong and did the problem slower. I got $12$ numbers from the numbers in $100!$, and then got another $8$ from $2 \times 4$, but, that can be applied for all the multiples of $2$ and $4$ that aren't of $8$. So, essentially, I am wondering if there is a quicker method for calculating this number without specifically counting out the numbers. Thanks in advance!

Answer 1

It's easiest, I think, to do this with powers of $2:$

$$\left\lfloor{100\over2}\right\rfloor+ \left\lfloor{100\over4}\right\rfloor+ \left\lfloor{100\over8}\right\rfloor+ \left\lfloor{100\over16}\right\rfloor+ \left\lfloor{100\over32}\right\rfloor+ \left\lfloor{100\over64}\right\rfloor=97=32\cdot3+1 $$

so the greatest exponent of $8$ is $32$.

Answer 2

I think the easiest way to answer this question is to factorize $100!$. Actually, a partial factorization will be sufficient. Thus, we see that $$100! = 2^{97} \times 3^{48} \times 5^{24} \times \ldots \times 83 \times 89 \times 97.$$

Since $8 = 2^3$, we need to divide $97$ by $3$ and discard the remainder. That is, rewrite $2^{96}$ as $8^n$ and there's your answer.

Answer 3

Just sum up the $2$-adic orders of the even numbers from $2$ to $100$

You get that $$(100)! = 2^{97}\cdot A=8^{32}\cdot 2A$$ where $A$ is the product of all the remaining (odd) factors of $100!$

Answer 4

Well $8^n = 2^{3n}$ so it will do to find the highest power of $2$ which divide $100!$.

Which means considering the prime factorization of $100!= 2^k*3^j*5^m.....$. What is $k$ in the $2^k$?

Well $100! = 1 * 2 * 3* 4* ....... *97*98*99*100$ but only the even numbers contribute to powers of $2$.

So $100! = 2*4*6*......*98*100*($ a bunch of odd terms$)=$

$= (2*1)*(2*2)*(2*3)*..... *(2*49)*(2*50)*($ the odd terms $)=$

$= 2^{50}*(1*2*3*4*.....*50)*($ the odd terms $)$.

Now the even terms of $1,2,3,4,...., 50$ are going to contribute to powers of $2$ so

$100! = 2^{50}*(2*4*6*...*48*50)*($ the odd terms up to fifty$)*($ a heck of a lot of odd terms$)=$

$2^{50}*(2*1)*(2*2)*(2*3)*.....*(2*24)*(2*25)*($ just a huge honkin amount of odd terms that we hae utterly no need to keep track of$)=$

$2^{50}*2^{25}*(1*2*3.....*25)*($ sh!tload of odd terms$)=$

$2^{50}*2^{25}*(2*4*....*24)*($ something odd $)=$

$2^{50}*2^{25}*2^{12}*(1*2*3*....*12)*($ odd monster $)=$

$2^{50}*2^{25}*2^{12}*(2*4*6*8*10*12)*($ odd thing $)=$

$2^{50}*2^{25}*2^{12}*2^6*(1*2*3*4*5*6)*$ ODD$)=$

$2^{50}*2^{25}*2^{12}*2^6*(2*4*6)*$ MEGA-ODD$)=$

$2^{50}*2^{25}*2^{12}*2^6*2^3*(1*2*3)*$ ODDasaurus $)=$

$2^{50}*2^{25}*2^{12}*2^6*2^3*2^1*$ MEGA-MECHA-ODD-atron-a-galactadingy.

So $100! = 2^{50+25+12+6+3+1}*M$ where $M$ is an odd number.

$100! = 2^{97}*M= 2^{3*32}*2*M= 8^{32}*2*M$.

So $8^{32}|100!$ but $8^{33}$ does not.

====

In general.

To find the highest power of prime $p$ that divides $N!$ realize that of the terms $1..... N$ that $[\frac Np]$ of those terms are mulitples of $p$ so $p^{[\frac Np]}$ will divide $N!$.

However $[\frac N{p^2}]$ of those terms are not just multiples of $p$ but of $p^2$ and these term contribute $[\frac N{p^2}]$ additional powers of $p$.

Repeating until we are done:

The highest power of $p$ dividing $100!$ will be $p^{[\frac Np] + [\frac N{p^2}] + [\frac N{p^3}] + ......}$.

In the case of $2$ and $100!$ it was

$2^{[\frac {100}2] + [\frac {100}4 ]+ [\frac {100}8] + [\frac {100}{16}[ + [\frac {100}{32}] + [\frac {100}{64}]}=2^{50 + 25 + 12+ 6 + 3+ 1}$.

Answer 5

So you're looking for roughly a third of $$n = \sum_{i = 1}^\infty \left\lfloor \frac{m}{p^i} \right\rfloor,$$ where $m = 100$ and $p$ is 2 ($m$ can be any positive integer and $p$ can be any odd prime).

Of course you don't actually have to even try to go to infinity. As soon as you notice $$\frac{m}{p^i} < 1,$$ you can stop the iteration.

The important thing to understand here is that each consecutive number by which you multiply to get a factorial "adds" its prime factors' exponents to the factorial's prime factors' exponents.

For example, $11! = 2^8 \times 3^4 \times 5^2 \times 7 \times 11 \times 13^0 \times 17^0 \times 19^0 \times \ldots$ Since $12 = 2^2 \times 3^{(1)}$, we can just add 2 to 2's exponent and 1 to 3's exponent, to obtain $12! = 2^{10} \times 3^5 \times 5^2 \times 7 \times 11 \times 13^0 \times$ $17^0 \times 19^0 \times \ldots$ And then the factorization of 13! is a simple matter of adding 1 to 13's exponent.

So in the specific case you're looking at, the first question is: how many numbers less than or equal to 100 are even? Half of them, giving you 50. But this doesn't account for how many of them are "doubly even," since they contribute at least 2 each to 2's exponent in the factorization of 100! So there's 25 of those, bringing our tally up to 75.

And then twelve of them are divisible by 8 (tally's 87 now), six are divisible by 16 (tally 93), three are divisible by 32 (tally 96), only one one is divisible by 64 (tally 97), and none are divisible by 128, 256, 512, 1024, etc. (tally stays at 97).

All that's left to do now is to solve $2^{97} = 8^x$, and round down $x$ if necessary.