AMC 10 · 2019 · #9

Grade 6 number-theory

Archetype Small-Domain Constrained Search

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

📏 Medium solution 💡 3 insights

Problem

What is the greatest three-digit positive integer $n$ for which the sum of the first $n$ positive integers is $\underline{not}$ a divisor of the product of the first $n$ positive integers?

$\textbf{(A) } 995 \qquad\textbf{(B) } 996 \qquad\textbf{(C) } 997 \qquad\textbf{(D) } 998 \qquad\textbf{(E) } 999$

Pick an answer.

(A)

995

(B)

996

(C)

997

(D)

998

(E)

999

View mode:

Toolkit + CCSS Solution

Understand

Restated: Find the largest three-digit positive integer $n$ such that the sum $1 + 2 + \cdots + n$ does NOT divide the product $1 \cdot 2 \cdots n = n!$.

Givens: Sum of first $n$ positive integers $= \dfrac{n(n+1)}{2}$; Product of first $n$ positive integers $= n!$; We want the largest $3$-digit $n$ where the sum does NOT divide the product; Choices: (A) $995$, (B) $996$, (C) $997$, (D) $998$, (E) $999$

Unknowns: The largest three-digit $n$ with the non-divisibility property

Understand

Restated: Find the largest three-digit positive integer $n$ such that the sum $1 + 2 + \cdots + n$ does NOT divide the product $1 \cdot 2 \cdots n = n!$.

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #5 Look for a Pattern, #3 Eliminate Possibilities

Numbers like $999$ are huge — Tool #9 says try small $n$ first ($n = 2, 3, 4, 5, 6, 7, \ldots$) 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.

Execute — Answer: B

#9 Solve an Easier Related Problem 4.OA.B.4 Step 1

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

$n = 2: S = 3, P = 2 \Rightarrow 3 \nmid 2$. $n = 3: S = 6, P = 6 \Rightarrow 6 \mid 6$. $n = 4: S = 10, P = 24 \Rightarrow 10 \nmid 24$. $n = 5: S = 15, P = 120 \Rightarrow 15 \mid 120$. $n = 6: S = 21, P = 720 \Rightarrow 21 \mid 720$. $n = 7: S = 28, P = 5040 \Rightarrow 28 \mid 5040$.

💡 Try the first handful of $n$ and watch which ones fail.

#5 Look for a Pattern 4.OA.B.4 Step 2

Spot the pattern.
The failures are $n = 2$ and $n = 4$.
Note: $n + 1 = 3$ (prime) and $n + 1 = 5$ (prime).
The successes have composite $n + 1$ ($n = 3 \Rightarrow n + 1 = 4$, $n = 5 \Rightarrow 6$, $n = 6 \Rightarrow 7$ — wait, $7$ is prime).
Test $n = 6$ again: $S = 21 = 3 \cdot 7$, $P = 720 = 2^4 \cdot 3^2 \cdot 5$ — there's no factor of $7$, so $21 \nmid 720$!
Let me recount: $n = 6$ FAILS.
Pattern: failures happen when $n + 1$ is prime.

$$n = 6: S = 21, P = 720, 720 / 21 = 34.28\ldots \Rightarrow 21 \nmid 720 \;\checkmark \text{ (failure)}$$

💡 Failures align exactly with $n + 1$ being prime.

#5 Look for a Pattern 6.NS.B.4 Step 3

Confirm WHY $n + 1$ prime causes failure.
The quotient is $\dfrac{P}{S} = \dfrac{n!}{n(n+1)/2} = \dfrac{2 \cdot (n - 1)!}{n + 1}$.
This is an integer iff $n + 1$ divides $2 \cdot (n - 1)!$.
If $n + 1$ is composite (and $> 4$), its prime factors are all $\le \dfrac{n + 1}{2} \le n - 1$, so they appear in $(n - 1)!$ and divide it.
If $n + 1$ is an odd prime $p$, then $p$ does not divide $(n - 1)! = (p - 2)!$ (none of $1, 2, \ldots, p - 2$ is divisible by $p$), and $p$ is odd so it doesn't divide $2$ either.
Failure.

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

💡 Cancel $n$ and the $\dfrac{1}{2}$; what's left is $\dfrac{2(n-1)!}{n+1}$ — fails only when $n + 1$ is an odd prime.

#3 Eliminate Possibilities 4.OA.B.4 Step 4

So the failing $n$ are exactly those with $n + 1$ prime.
We want the largest three-digit $n$ such that $n + 1$ is prime — scan the answer choices from largest down.

$$n = 999: n + 1 = 1000 = 2^3 \cdot 5^3 \text{ (composite)}$$

💡 $1000$ is obviously not prime.

#3 Eliminate Possibilities 4.OA.B.4 Step 5

$n = 998$: $n + 1 = 999 = 3 \cdot 333 = 3^3 \cdot 37$.
Composite.

$$999 = 3 \cdot 333$$

💡 Digit sum $9 + 9 + 9 = 27$ divisible by $3$, so $999$ is divisible by $3$.

#3 Eliminate Possibilities 4.OA.B.4 Step 6

$n = 997$: $n + 1 = 998 = 2 \cdot 499$.
Composite.

$$998 = 2 \cdot 499$$

💡 $998$ is even, so divisible by $2$.

#3 Eliminate Possibilities 4.OA.B.4 Step 7

$n = 996$: $n + 1 = 997$.
Check $997$ for primality: not divisible by $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31$ (test primes up to $\sqrt{997} \approx 31.6$).
$997 / 7 = 142.4\ldots$, $997 / 11 = 90.6\ldots$, $997 / 13 = 76.7\ldots$, $997 / 17 = 58.6\ldots$, $997 / 19 = 52.5$ exact?
$19 \cdot 52 = 988$, $997 - 988 = 9$, no.
$997 / 23 = 43.3\ldots$, $997 / 29 = 34.4\ldots$, $997 / 31 = 32.2\ldots$.
None divide.
So $997$ is prime.

$$997 \text{ is prime}$$

💡 Test small primes up to $\sqrt{997}$; none divide, so $997$ is prime.

#3 Eliminate Possibilities 4.NBT.A.2 Step 8

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

$$n = 996 \Rightarrow \textbf{(B)}$$

💡 First choice (from the top) where $n + 1$ is prime.

[1] #9 4.OA.B.4 Test small cases. For each $n$, compute $S = \dfrac{n(n+1)}{2}$ and $P = n!$, th

[2] #5 4.OA.B.4 Spot the pattern. The failures are $n = 2$ and $n = 4$. Note: $n + 1 = 3$ (prime

[3] #5 6.NS.B.4 Confirm WHY $n + 1$ prime causes failure. The quotient is $\dfrac{P}{S} = \dfrac

[4] #3 4.OA.B.4 So the failing $n$ are exactly those with $n + 1$ prime. We want the largest thr

[5] #3 4.OA.B.4 $n = 998$: $n + 1 = 999 = 3 \cdot 333 = 3^3 \cdot 37$. Composite.

[6] #3 4.OA.B.4 $n = 997$: $n + 1 = 998 = 2 \cdot 499$. Composite.

[7] #3 4.OA.B.4 $n = 996$: $n + 1 = 997$. Check $997$ for primality: not divisible by $2, 3, 5,

[8] #3 4.NBT.A.2 $n = 996$ is the largest three-digit $n$ with $n + 1$ prime. So the sum does not

Review

Reasonableness: Quick sanity check on $n = 996$: $S = \dfrac{996 \cdot 997}{2} = 498 \cdot 997$. $P = 996!$. The quotient is $\dfrac{2 \cdot 995!}{997}$, and since $997$ is prime and larger than every factor in $995!$, the denominator $997$ does not cancel — so $S \nmid P$. ✓. Conversely for $n = 997$: $\dfrac{2 \cdot 996!}{998} = \dfrac{2 \cdot 996!}{2 \cdot 499} = \dfrac{996!}{499}$, and $499$ appears as one of the factors of $996!$ (since $499 < 996$), so the quotient is an integer — $S \mid P$. So $997$ does NOT satisfy the condition, confirming $996$ is the right answer.

Alternative: Tool #6 (Guess and Check) on the answer choices alone — from (E) down, verify divisibility directly: $999 + 1 = 1000$ obviously composite, $998 + 1 = 999$ digit sum divisible by $3$, $997 + 1 = 998$ even, $996 + 1 = 997$ — check primes up to $\sqrt{997}$, none divide, so $997$ prime, stop. Same answer.

CCSS standards used (min grade 6)

4.OA.B.4 Find all factor pairs and recognize multiples; determine prime or composite (Testing whether $n + 1$ is prime or composite for $n + 1 \in \{1000, 999, 998, 997\}$, and connecting primality to the divisibility condition.)
6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Simplifying $\dfrac{n!}{n(n + 1)/2} = \dfrac{2(n-1)!}{n + 1}$ by canceling shared factors of $n$ and $\dfrac{1}{2}$.)
4.NBT.A.2 Read and write multi-digit whole numbers and compare using symbols (Matching $n = 996$ to answer choice (B).)

⭐ This AMC 10 problem only needs Grade 6 factoring you already know — the sum $\dfrac{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$.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: B

Review

CCSS standards used (min grade 6)

More like this