2019 AMC 12A Problem 24

Compare the exponent of a prime $p$ in numerator and denominator using $v_p(m!) = \dfrac{m - s_p(m)}{p - 1}$

Failure requires $n$ to be a prime power $p^a$ with $p^a - 1 \lt 2a(p - 1)$

Fix a prime $p\le n.$ By Legendre’s formula, the difference between the exponent of $p$ in the numerator and its exponent in the denominator is $$\begin{aligned} D_p &=\sum_{k\ge1}\left\lfloor\dfrac{n^2-1}{p^k}\right\rfloor\\ &\quad-n\sum_{k\ge1}\left\lfloor\dfrac{n}{p^k}\right\rfloor. \end{aligned}$$ If $r_k$ is the remainder of $n$ modulo $p^k,$ the $k$th summand is $\left\lfloor\dfrac{nr_k-1}{p^k}\right\rfloor.$

Let $a=v_p(n).$ The first $a$ summands are $-1.$ If $n$ is not a power of $p,$ write $n=p^a m$ with $m\ge2.$ When $a\ge1,$ the next summand is at least $\dfrac{n}{p}-1\ge a,$ and all later summands are nonnegative; when $a=0,$ every summand is already nonnegative. Thus $D_p\ge0$ unless $n$ is a power of $p.$

For $n=p^a,$ Legendre’s formula reduces the requirement to $p^a-1\ge2a(p-1).$ Among prime powers at most $50,$ this fails exactly when $a=1$ (so $n$ is prime) and when $n=2^2=4.$ There are $15$ primes at most $50,$ plus $n=4,$ giving $16$ failures. Hence $50 - 16 = 34$ values of $n$ work.

Thus, the correct answer is D.