For how many integers $n$ is $\frac{(n^3)!}{(n!)^{n^2-1}((n^2+1)!-(n^2)!)}$ an integer?

Question

I'm asked to find the number of integers $n$ from 1 to 100, inclusive, such that $$\frac{(n^3)!}{(n!)^{n^2-1}((n^2+1)!-(n^2)!)}$$ is an integer. This problem was from our test and was a bonus problem created by my crazy math teacher. How do I even begin? This expression looks too daunting for me to even attempt, and I can't see any easy simplifications. The answer says $\boxed{74}$ integers. How do I begin? EDIT: SORRY: The answer is $\boxed{74}$, not 84. My bad! Typo

Answer 1

I started out writing this answer assuming that your teacher's result was correct. I have left this reasoning in the answer since it might be of interest to you as to how you might tackle problems of this sort. However, it would have been easier to only consider $n$ prime to demonstrate that the result of $84$ is incorrect.

Preliminary Result 1 Let $a,b,t$ be integers such that $n=at+b,t>b\ge0$. Then $$\left\lfloor \frac{n^3}{t}\right\rfloor-\left\lfloor \frac{n^2}{t}\right\rfloor-(n^2-1)\left\lfloor \frac{n}{t}\right\rfloor=a+ab(b-1)+an(b-1)+\left\lfloor \frac{b^3}{t}\right\rfloor-\left\lfloor \frac{b^2}{t}\right\rfloor.$$

Proof

The result follows immediately upon substituting $n^2=(an+ab)t+b^2$ and $n^3=(an^2+abn+ab^2)t+b^3.$

Note that this expression is positive if $b>0$.

Preliminary Result 2
For any prime $p$ the power of $p$ dividing the numerator and denominator of the given expression are, respectively, as follows. $$\left\lfloor \frac{n^3}{p}\right\rfloor+\left\lfloor \frac{n^3}{p^2}\right\rfloor+...$$ $$\left\lfloor \frac{n^2}{p}\right\rfloor+\left\lfloor \frac{n^2}{p^2}\right\rfloor+...+(n^2-1)\left(\left\lfloor \frac{n}{p}\right\rfloor+\left\lfloor \frac{n}{p^2}\right\rfloor+...\right)+v_p(n^2)$$

Proof

This is an application of the standard result for prime divisors of $n!$

When is the given expression an integer?

Suppose it is not an integer. Then there must be a prime $p$ for which the power of $p$ dividing the numerator is less than that dividing the denominator. Applying the two preliminary results and with $t=p,p^2,p^3,...$, we see that this can only occur for a prime divisor $p$ of $n$.

However, as a test of your teacher's result let us consider just the case $n=p$. Applying Preliminary Result 2 we obtain $p^2+p+1$ for the power of $p$ dividing the numerator and $p^2+p+2$ for the power of $p$ dividing the denominator. So the expression is not an integer for any of the $25$ primes less than $100$.

Answer 2

It can done as distribution of $n^3$ number of distinct objects into $n^2$ number of identical groups such that each group get exactly $n$ objects and other factor $\frac{(n-1)!}{n}$ is not an integer if $n$ is a prime number. In first 100 natural number there are 25 numbers. For detailed solution you can check here https://www.mathsdiscussion.com/discussion-forum/topic/distribution-of-distinct-objects-2/?part=1#postid-100