Prove quotient of factorials is integral

Solution 1:

This is a gross brute force answer.

We will show that for any positive integer $D$:

$$0\leq\left\lfloor\frac{30n}{D}\right\rfloor + \left\lfloor\frac{n}{D}\right\rfloor - \left\lfloor\frac{15n}{D}\right\rfloor - \left\lfloor\frac{10n}{D}\right\rfloor - \left\lfloor\frac{6n}{D}\right\rfloor$$

This is enough to show your theorem because when $D=p^k$ is a prime power, this is the total number of multiples of $p^k$ in the numerator minus the total number of multiples of $p^k$ in the denominator.

Write $30n = Dq+r$ for some $0\leq r < D$. Then the right hand side is:

$$q + \left\lfloor\frac{q}{30}\right\rfloor - \left\lfloor\frac{q}{2}\right\rfloor - \left\lfloor\frac{q}{3}\right\rfloor - \left\lfloor\frac{q}{5}\right\rfloor$$

Writing $q=30p+s$ with $0\leq s<30$, we see this is:

$$30p +s + p - 15p -\left\lfloor\frac{s}{2}\right\rfloor - 10p - \left\lfloor\frac{s}{3}\right\rfloor - 6p- \left\lfloor\frac{s}{5}\right\rfloor\\=s-\left\lfloor\frac{s}{2}\right\rfloor - \left\lfloor\frac{s}{3}\right\rfloor - \left\lfloor\frac{s}{5}\right\rfloor$$

If this is non-negative for $s=0,...,29$ you are done. You can brute force from there.

Note

It seems like there should be some direct proof for:

$$0\leq s-\left\lfloor\frac{s}{2}\right\rfloor - \left\lfloor\frac{s}{3}\right\rfloor - \left\lfloor\frac{s}{5}\right\rfloor$$

for $s=0,\dots,29$. However, it is not true for $s=30$.