AMC 10 · 2019 · #9

Grade 6 number-theory

Archetype Small-Domain Constrained Search └ Sub-archetype Factor / Divisibility Constraint

factorialprime-numbersdivisibility-rulestriangular-numbersprimality-test identify-subproblemspattern-recognition ↑ Prerequisites: factorialprime-numbersdivisibility-rules

📏 Medium solution 💡 3 insights

Problem

Find the largest three-digit positive integer n such that the sum 1 + 2 + … + n does NOT divide the product 1 · 2 … n = n!.

Pick an answer.

(A)

995

(B)

996

(C)

997

(D)

998

(E)

999

AMC 10 2019 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve

Strategy Solve an Easier Related Problem

Numbers like 999 are huge — Tool #9 says try small n first (n = 2, 3, 4, 5, 6, 7, …) and see when the sum divides the product and when it doesn't. Tool #5 spots the pattern (only special n fail). Tool #3 then scans the answer choices from largest to smallest to find the first one satisfying the condition.

1STEP 1

Test small cases. For each n, compute S = $\frac{n(n+1)}{2}$ and P = n!, then check whether S ∣ P.

n = 2: S = 3, P = 2 → 3 ∤ 2. n = 3: S = 6, P = 6 → 6 ∣ 6. n = 4: S = 10, P = 24 → 10 ∤ 24. n = 5: S = 15, P = 120 → 15 ∣ 120. n = 6: S = 21, P = 720 → 21 ∣ 720. n = 7: S = 28, P = 5040 → 28 ∣ 5040.

2STEP 2

Failures hit at n = 2, 4, 6 — each has n + 1 prime (3, 5, 7); successes have composite n + 1. Conjecture: it fails when n + 1 is prime.

n = 6: S = 21, P = 720,

\frac{720}{21}

= 34.28… → 21 ∤ 720 ✓ (failure)

3STEP 3

Simplify: $\frac{P}{S}$ = $\frac{2(n - 1)!}{n + 1}$ . Composite n + 1 cancels into (n - 1)!; an odd prime n + 1 divides neither (n - 1)! nor 2, so it fails.

\frac{n!}{\frac{n(n+1)}{2}}

\frac{2(n-1)!}{n+1}

4STEP 4

Failing n are exactly those with n + 1 prime, so scan the choices from the top. n = 999 → n + 1 = 1000 = 2³ · 5³, composite. Move down.

n = 999: n + 1 = 1000 = 2³ · 5³ (composite)

5STEP 5

n = 998 → n + 1 = 999 = 3 · 333 = 3³ · 37, composite. Keep going.

999 = 3 · 333

6STEP 6

n = 997 → n + 1 = 998 = 2 · 499, composite. Still not it.

998 = 2 · 499

7STEP 7

n = 996 → n + 1 = 997; testing primes up to √997 ≈ 31, none divide, so 997 is prime — the sum fails to divide here.

997 is prime

8STEP 8

So n = 996 is the largest three-digit n with n + 1 prime — the sum does not divide the product. Answer (B).

n = 996 → (B)

Answer

996

Quick sanity check on n = 996: S =

\frac{996 · 997}{2}

= 498 · 997. P = 996!. The quotient is

\frac{2 · 995!}{997}

, and since 997 is prime and larger than every factor in 995!, the denominator 997 does not cancel — so S ∤ P. ✓. Conversely for n = 997:

\frac{2 · 996!}{998}

\frac{2 · 996!}{2 · 499}

\frac{996!}{499}

, and 499 appears as one of the factors of 996! (since 499 ＜ 996), so the quotient is an integer — S ∣ P. So 997 does NOT satisfy the condition, confirming 996 is the right answer.

💡Key takeaway

This AMC 10 problem only needs Grade 6 factoring you already know — the sum $\frac{n(n+1)}{2}$ divides n! except when n + 1 is an odd prime. Among the answer choices, 1000, 999, 998 all have composite (n + 1), but n = 996 gives n + 1 = 997, which is prime. So n = 996.

More like this