2019 AMC 10A Problem 9

The sum of the first $n$ positive integers is $\frac{n(n+1)}{2}$, and their product is $n! = 1 \cdot 2 \cdots n$.

1. Look at a small case first. Take $n = 4$: the sum is $10$ and the product is $24$. $10$ does not divide $24$. Now $n = 5$: the sum is $15$ and the product is $120 = 15 \cdot 8$. It divides.
2. Divide in general. Write $n! = n \cdot (n-1)!$. Then
$$\frac{n!}{\;n(n+1)/2\;} = \frac{2 \cdot n \cdot (n-1)!}{n(n+1)} = \frac{2 \cdot (n-1)!}{n+1}.$$
So the question is whether $n + 1$ divides $2 \cdot (n-1)!$, that is, $2 \cdot 1 \cdot 2 \cdots (n-1)$.
3. When $n + 1$ is a prime (bigger than $2$): a prime divides a product only if it divides one of the factors. Every factor here is smaller than $n + 1$, so none of them is a multiple of it. The sum is not a divisor. (In step 1, $n + 1 = 5$ is prime.)
4. When $n + 1$ is not prime, it splits into smaller factors that all show up among $1, 2, \ldots, n-1$ (with plenty of room when $n$ is this large). So the sum is a divisor.
5. Search from the top. We want the largest three-digit $n$ with $n + 1$ prime.
- $n = 999$: $n + 1 = 1000$, not prime.
- $n = 998$: $n + 1 = 999 = 27 \cdot 37$, not prime.
- $n = 997$: $n + 1 = 998 = 2 \cdot 499$, not prime.
- $n = 996$: $n + 1 = 997$. Try every prime up to $31$ (since $32^2 = 1024 > 997$): none divides $997$. So $997$ is prime.

The largest such $n$ is $996$.

The answer is $\boxed{\textbf{(B)}\ 996}$.

Simplifying the fraction first turned a question about two big formulas into "does $n + 1$ divide a product of smaller numbers?" A prime can never divide a product of numbers all smaller than itself, which is exactly why primes are the failures. Cancel what you can before thinking about divisibility.

The sum is $\frac{n(n+1)}{2}$ and the product is $n!$. Their quotient is
$$\frac{n!}{n(n+1)/2} = \frac{2\,(n-1)!}{n+1},$$
so the sum divides the product exactly when $n + 1$ divides $2(n-1)!$.

If $n + 1$ is a prime $p > 2$, then $p$ divides none of the factors $1, 2, \dots, n - 1$ nor the $2$, so $p$ does not divide $2(n-1)!$: the sum is not a divisor. If $n + 1$ is composite, its prime factors are all at most $(n+1)/2 \le n - 1$ and appear (with room to spare) inside $2(n-1)!$, so the sum does divide the product.

So we need the largest three-digit $n$ with $n + 1$ prime. Check downward: $1000$, $999 = 27 \cdot 37$, and $998 = 2 \cdot 499$ are composite, while $997$ is prime (it has no prime factor up to $31$). Hence $n = 996$.

The answer is $\boxed{\textbf{(B)}\ 996}$.