2019 AMC 10A Problem 9

Attempt Problem 9 of the 2019 AMC 10A below, then check your answer against the professionally curated solution from LIVE by Po-Shen Loh. You can also try the full timed exam, view all 2019 AMC 10A solutions, or check the answer key.

All problems are used with official legal permission of the Mathematical Association of America (MAA).

9.

What is the greatest three-digit positive integer nn for which the sum of the first nn positive integers is not a divisor of the product of the first nn positive integers?

995995

996996

997997

998998

999999

Answer: B
Concepts:factorialdivisibilityprime
Difficulty rating: 1420
Solution:

The sum of the first nn numbers is n(n+1)2.\dfrac{n(n + 1)}{2}. We need this to not divide n!.n!.

Put m=n+1m=n+1. If mm is composite, write m=abm=ab with 2ab2\le a\le b. When a<ba<b, the distinct factors aa and bb both occur in (m2)!=(n1)!(m-2)!=(n-1)!. When a=ba=b, we have a3a\ge3, and the two multiples aa and 2a2a both occur in (m2)!(m-2)!, so a2=ma^2=m divides that factorial as well. Thus m(n1)!m\mid(n-1)!, and consequently n(n+1)2n!.\frac{n(n+1)}2\mid n!.

Conversely, if n+1n+1 is prime, that prime factor does not occur in n!n!, so the divisibility fails. Since 997997 is prime while 998,999,998,999, and 10001000 are composite, the greatest three-digit value is 9971=996.997-1=996.

Thus, B is the correct answer.

← Problem 8#8
Full Exam

Problem 9 in Other Years