What is the smallest n integer number such that 24^n does not divide 50!

Question

What is the smallest n integer number such that 24^n does not divide 50! (factorial) ?

This is what I've done so far, but it seems a bit complicated

Answer 1

$24=\color\red{2^3}\cdot\color\green{3^1}$

---

The multiplicity of $\color\red{2}$ in $50!$ is $\sum\limits_{n=1}^{\log_{\color\red{2}}50}\Big\lfloor\frac{50}{\color\red{2}^n}\Big\rfloor=25+12+6+3+1=\color\red{47}$

---

The multiplicity of $\color\green{3}$ in $50!$ is $\sum\limits_{n=1}^{\log_{\color\green{3}}50}\Big\lfloor\frac{50}{\color\green{3}^n}\Big\rfloor=16+5+1=\color\green{22}$

---

Therefore:

• The maximum value of $n$ such that $(\color\red{2^3})^n$ divides $50!$ is $\Big\lfloor\frac{\color\red{47}}{\color\red{3}}\Big\rfloor=15$
• The maximum value of $n$ such that $(\color\green{3^1})^n$ divides $50!$ is $\Big\lfloor\frac{\color\green{22}}{\color\green{1}}\Big\rfloor=22$

---

Therefore:

• The maximum value of $n$ such that $24^n$ divides $50!$ is $\min(15,22)=15$
• The minimum value of $n$ such that $24^n$ does not divide $50!$ is $15+1=16$

Answer 2

We know that any integer is the product of some prime numbers raised to some exponents. We also know that one prime number divides no prime number other than itself, so if $\frac{a}{b}$ is an integer, and given that $a = p_1^{\alpha_1}\times...\times p_n^{\alpha_n}$ and $b = q_1^{\beta_1}\times...\times q_m^{\beta_m}$, we get:

$$\frac{p_1^{\alpha_1}\times...\times p_n^{\alpha_n}}{q_1^{\beta_1}\times...\times q_m^{\beta_m}} \in \mathbb{Z}$$ if and only if we can "cross out" all numbers in the denominator. That means of simplifying a fraction can only be carried out when the number appears both in the numerator AND denominator. (I am talking about this so-loved rule:)

$$\frac{ab}{ac} = \frac{\not{a}b}{\not{a}c} = \frac{b}{c}$$That would mean all $q_i$ appear in the factorization of $a$, and furthermore each $q_i$ would appear at least $\beta_i$ times.

Now you have that $24 = 2^3\times 3^1$ so $24^k = (2^3\times 3^1)^k = (2^3)^k\times (3^1)^k = (2^{3k})(3^k)$

So if $24^k$ is to divide $50!$, then (and because of the prime factorization of $24^k$), $50!$ must have at least $3k$ numbers 2 and $k$ numbers 3 in its prime factorization.

Now you stop for a second and realizing that

$$50! = 50\times49\times48\times...\times2\times1$$

you know that the prime factorization of $50!$ is just the products of all the prime factorizations of the numbers $1$ through $50$. Keeping this train of thought, you know that there are 25 even numbers between 1 and 50, so there are 25 numbers in the product $50! = 50\times49\times48\times...\times2\times1$ that contribute with a 2 for the factorization. Now 1 out of every 4 numbers contributes with an extra 2 (because 1 out of every 4 numbers is divisible by 4, which means they are divisible by 2 two times). And then 1 out of every 8 contributes with another 2. And so on and so forth. You can do the same reasoning for the 3, and then you should arrive at the value that $k$ must have so that $24^k$ divides $50!$

Answer 3

We know we can write every number as a product of primes. Now, $24=2^3\cdot 3$, so $$24^k = 2^{3k}\cdot 3^{k}$$

Now, we also know that

$$50! = 2^m 3^n \cdot x$$

for some $x$ which is not divisible by $2$ or $3$.

So, we see that $24^k$ divides $50!$ if and only if it divides $2^m2^n$, and this is only true if $m<3k$ and $n<k$.

So, if you calculate $n$ and $m$, you should be able to answer this question.

---

Let's see how we can calculate $m$, i.e., how many twos are in $50!$.

• First of all, multiplying by $32$ gives $5$ twos.
• Multiplying by any multiple of $16$ gives $4$ twos. There are $3$ multiples of $50$ smaller than $50$, but we already counted $32$, so we are left with $16$ and $48$ which both gave $4$ twos, a total of $8$.
• Multples of $8$: There are 6 of them, $3$ were aleady counted, so the remaing $3$ give $3$ twos each, a total of $9$.
• Multiples of $4$: 12 in total, $6$ already counted, the remaining $6$ give two twos each for a total of $12$.
• Multiples of $2$: $25$ in total, of which $13$ weren't counted, so $13$ twos.

all together, we have $5+8+9+12+13=47$ twos, so $m=47$

Answer 4

As shown in this answer, the number of factors of a prime $p$ that divides $n!$ is $$ \frac{n-\sigma_p(n)}{p-1} $$ where $\sigma_p(n)$ is the sum of the digits in the base-$p$ representation of $n$.

Since $50=110010_\text{two}$, the number of factors of $2$ in $50!$ is $$ \frac{50-3}{2-1}=47 $$ Since $50=1212_\text{three}$, the number of factors of $3$ in $50!$ is $$ \frac{50-6}{3-1}=22 $$ Since $24^n=2^{3n}\cdot3^n$, the smallest $n$ so that $3n\gt47$ or $n\gt22$ is $n=16$.