If $n$ is an integer $\gt 0$, prove


is also an integer. I understand that a general approach is proving that the power of any prime factor is greater in the numerator than it is in the denominator, but I haven't been able to formulate this into a rigorous proof.

  • $\begingroup$ Hopefully, the square brackets were only meant for grouping. Please respond if not. Regards $\endgroup$ – Amzoti Jan 15 '13 at 19:57
  • $\begingroup$ any suggestions anyone? $\endgroup$ – Rebecca Kuang Jan 15 '13 at 21:06
  • $\begingroup$ The following question is relevant: mathoverflow.net/questions/26336/…. $\endgroup$ – mjqxxxx Jan 16 '13 at 6:32

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.


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$.

  • $\begingroup$ Again, I see that these all three are necessarily integers, but not that the bottom term necessarily divides the product of the top two. Does this require analyzing the powers of an arbitrary prime for the numerator and denominator? I end up with an inequality that I don't see any easy way to solve.... $\endgroup$ – Rebecca Kuang Jan 15 '13 at 20:24
  • $\begingroup$ Okay, updated to be almost a full answer. @RebeccaKuang $\endgroup$ – Thomas Andrews Jan 16 '13 at 0:45

Here is a short video which shows, among other things, how to compute the highest power of a prime number that will divide a given factorial. Perhaps you could use the method in the video to compute the maximum powers of the common prime factors (2,3,5,7 etc.) in the numerator and the denominator say using $n=1$ as a base case. Then use an inductive step for $n+1$ to develop a proof to show that all the prime factors up to the highest prime factor in the denominator (which will not exceed $kn$ in $kn!$) are also prime factors in the numerator and that the powers of these common prime factors are always higher in the numerator in your problem. Consequently, the fraction will always be an integer.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.