Whether m divides n! or not?

Question

I have a big number ($n!$). And I want to know whether $n!$ dividable by $m$ or not.

Well calculating $n!$ is not a good idea so I'm looking for another way.

Example:

$9$ divides $6!$

$27$ does not divide $6!$

$10000$ divides $20!$

$100000$ does not divide $20!$

$1009$ does not divide $1000!$ (of course I cannot calculate $1000!$)

Thank you.

Answer 1

As noted in the comments, the best way to find this out is to look at the prime factorizations of $m$ and $n!$. I will assume that you have the computational ability to obtain the prime factorization of $m$ such that $m=\prod_i p_i^{\alpha_i}$ where $p_i$ is the $i^{th}$ prime ($p_1=2$) and $\alpha_i\in\Bbb N_0$. Now, there is a handy result that says that, given a prime $p_i$ and a natural number $n$, the greatest integer $\beta_i$ such that $p_i^{\beta_i}\mid n!$ is: $$ \beta_i=\sum_{k=1}^{\lfloor \log_{p_i}n\rfloor}\left\lfloor\frac{n}{p_i^k}\right\rfloor $$

Now all you need to do is appreciate $(\forall i\in\Bbb N: \alpha_i\le\beta_i)\iff m\mid n!$

In other words, if you verify $\alpha_i\le\beta_i$ for all $i$, you're done.

---

Here's an example from your question: $$10\,000=10^4=2^4\cdot5^4$$

So you only need to show $2^4\mid 20!$ and $5^4\mid 20!$.

$$ \begin{align}\beta_1&=\sum_{k=1}^{\lfloor \log_2 20\rfloor}\left\lfloor\frac{20}{2^k}\right\rfloor=\sum_{k=1}^{4}\left\lfloor\frac{20}{2^k}\right\rfloor=\left\lfloor\frac{20}{2}\right\rfloor+\left\lfloor\frac{20}{4}\right\rfloor+\left\lfloor\frac{20}{8}\right\rfloor+\left\lfloor\frac{20}{16}\right\rfloor=18\ge 4\\ \beta_3&=\sum_{k=1}^{\lfloor \log_5 20\rfloor}\left\lfloor\frac{20}{5^k}\right\rfloor=\left\lfloor\frac{20}{5}\right\rfloor=4\ge 4 \end{align}$$ Since all other $\alpha_i=0$, trivially $\beta_i\ge \alpha_i$. Consequently, $10^4\mid 20!$

If you were to increase $m$ to $10^5$, you would notice $\alpha_3=5$ and so $\beta_3\not\ge\alpha_3$ therefore $10^5\not\mid 20!$

Answer 2

Let's analyse first $m$ as a product of primes: $$ m=2^{\ell_1}3^{\ell_2}\cdots p_k^{\ell_k}. $$ Then $m$ divides $n!$ if and only if $2^{\ell_1}$ and $3^{\ell_2}$ and $\cdots$ and $p_k^{\ell_k}$ divide $n!$.

The question now which remains to be answered is the following:

Which is the largest value of $k$, such that $p^k$ divides $n!$? (Where $p$ a prime number)

The answer is $$ k= \left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\cdots $$ where $\lfloor x\rfloor$ is the integer part of $x$. Note that the sum above is finite, as $\left\lfloor\frac{n}{p^j}\right\rfloor=0$, if $p^j>n$.