Factors of factorials

Question

There is a question on factorials:

Q: What is the largest possible integer value of $n$ if $4^n$ divides $16!$ evenly.

According to an explanation, the question is asking 'how many factors of $4$ there are in $16!$'. But then it is solved by counting the number of $2$s among the even factors of $16!$ ($16, 14, 12, ...$). I don't understand the solution steps. Is it possible to provide an explanation for this solution strategy?

Thank you.

Answer 1

For primes $p$, it is relatively simple to determine the power with which it divides a factorial $m!$ $$ \left\lfloor \frac mp\right\rfloor + \left\lfloor \frac m{p^2}\right\rfloor + \left\lfloor \frac m{p^3}\right\rfloor+\ldots$$ because there are so many multiples of $p$ among the factors defining $m!$, plus so many multiples of $p^2$ (i.e., of another $p$), plus so many multiples of $p^3$ (i.e., of yet another $p$), and so on. This simple argument does not work for composite numbers in place of $p$, simply because divisibility can be "collected" from diffferent factors.

However, knowing the power for the prime $2$, you can easily find out the power for $4=2^2$.

Answer 2

With a non-prime such as $4$, you've got the problem that factors from terms that individually are not a multiple of $4$ may combine to a factor of $4$. This massively complicates the calculation. For example, consider $$6! = 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$$ The only factor that is divisible by $4$ is $4$ itself, so you might wrongly conclude the highest power of $4$ in $6!$ is $4^1=4$. However $6\cdot 2=12 = 3\cdot 4$, so there's another factor of $4$ "hidden" in the other factors. And indeed, $6! = 720 = 4^2\cdot 45$.

With prime factors you don't have this problem, as those cannot arise from a product unless they are in one of the factors. So to determine how many of them are in the product, it is sufficient to add up those found in the factors. For example, to determine the $2$s in $6!$, you find one factor $2$ in $6$, two of them in $4$, and one further in $2$, to give a total of $4$.

Now $4=2^2$, therefore $2^4=4^2$. More generally, if you want to know the largest power of $k$ in $n!$, you do the following:

1. Determine the prime factorization of $k$, i.e. $$k = {p_1}^{i_1} \cdot {p_2}^{i_2} \cdots {p_m}^{i_m}$$

2. For each of the primes of that prime factorization, determine the highest power that dividen $n!$ (the formula Hagen von Eitzen gave is very useful for this). That is, $$n! = {p_1}^{j_1}\cdot{p_2}^{j_2}\cdots{p_m}^{j_m}\cdot X$$ where $\gcd(X,k)=1$.

3. Now the maximal power of $k$ in $n!$ is $$\min\left\{\left\lfloor\frac{i_1}{j_1}\right\rfloor, \left\lfloor\frac{i_2}{j_2}\right\rfloor,\ldots,\left\lfloor\frac{i_m}{j_m}\right\rfloor\right\}$$

In your case, $k=4$ and $n=16$, so you get

1. $4 = 2^2$, so the only prime you have to consider is $2$

2. The exponent of $2$ in $16!$ is $8+4+2+1 = 15$, that is, $16! = 2^{15}\cdot X$ with $X$ odd

3. The exponent you're looking for is therefore $$\min\left\{\left\lfloor\frac{15}{2}\right\rfloor\right\} = 7$$

A more complicated question could be the maximal power of $18$ in $100!$. But it's again easily solved using that algorithm:

1. $18 = 2^1\cdot 3^2$

2. Exponents in $100!$:

   • Exponent of $2$: $50+25+12+6+3+1 = 97$

   • Exponent of $3$: $33+11+3+1 = 48$

3. The maximal exponent then is $$\min\left\{\left\lfloor\frac{97}{1}\right\rfloor,\left\lfloor\frac{48}{2}\right\rfloor\right\} = 24$$