2019 AMC 10A Problem 25

One fact that greatly helps with this problem is realizing that $$\dfrac{(n^2)!}{(n!)^{n + 1}}$$ is always an integer. This is because it is the number of ways to split up $n^2$ objects into $n$ unordered groups of size $n.$ Now, we get that $$\dfrac{(n^2 - 1)!}{(n!)^n} = \dfrac{(n^2)!}{(n!)^{n + 1}} \cdot \dfrac{n!}{n^2}.$$ Therefore, whenever $n^2$ divides $n!,$ the original expression is an integer; this is equivalent to $n$ dividing $(n - 1)!.$ Suppose $n$ is composite. If $n=ab$ with $2\le a<b<n$, then the distinct factors $a$ and $b$ both occur in $(n-1)!$, so $(n-1)!$ is divisible by $n$. If $n=a^2$ with $a\ge3$, then $(n-1)!$ contains the distinct factors $a$ and $2a$, whose product is a multiple of $n$. Thus every composite $n\ne4$ works. The case $n=1$ also works directly. Conversely, if $n=p$ is prime, the exponent of $p$ in the denominator is $p,$ while its exponent in $(p^2-1)!$ is $p-1,$ so the expression is not an integer. For $n=4,$ the denominator contains $2^{12},$ while $15!$ contains only $2^{11},$ so this case also fails. There are $15$ primes at most $50,$ and adding $4,$ we get $16$ values for $n$ that do not work. Therefore, the desired answer is $50 - 16 = 34.$ Thus, D is the correct answer.