AMC 10 · 2005 · #22
Grade 7 number-theoryFor how many positive integers n less than or equal to 24 is n! evenly divisible by 1+2+⋯+n?
Pick an answer.
AMC 10 2005 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.
Try it yourself first — the explanation is most useful after you’ve attempted it.
Toolkit + CCSS Solution
Understand
Restated: Count the positive integers $n$ with $1 \le n \le 24$ for which $n!$ is divisible by the sum $1 + 2 + \cdots + n$.
Givens: $n$ ranges over the positive integers from $1$ to $24$; The divisor is the running sum $1 + 2 + \cdots + n$; The dividend is $n! = 1 \cdot 2 \cdot 3 \cdots n$; Answer choices: (A) $8$, (B) $12$, (C) $16$, (D) $17$, (E) $21$
Unknowns: How many of the $24$ values of $n$ make $n!$ divisible by $1 + 2 + \cdots + n$
Understand
Restated: Count the positive integers $n$ with $1 \le n \le 24$ for which $n!$ is divisible by the sum $1 + 2 + \cdots + n$.
Givens: $n$ ranges over the positive integers from $1$ to $24$; The divisor is the running sum $1 + 2 + \cdots + n$; The dividend is $n! = 1 \cdot 2 \cdot 3 \cdots n$; Answer choices: (A) $8$, (B) $12$, (C) $16$, (D) $17$, (E) $21$
Plan
Primary tool: #16 Change Focus / Count the Complement
Secondary: #4 Introduce a Variable, #5 Look for a Pattern
Checking all $24$ values one by one is slow, so Tool #4 (Introduce a Variable) first replaces the sum with the formula $\frac{n(n+1)}{2}$ and simplifies the quotient into one clean fraction — that turns a divisibility puzzle about $n!$ into a question about a single factor $n+1$. Tool #5 (Look for a Pattern) then tests what kind of $n+1$ breaks the divisibility, and the pattern is sharp: it fails exactly when $n+1$ is an odd prime and works every other time. Because the failures are the rare cases, Tool #16 (Count the Complement) is the efficient finish — count the odd primes that fail and subtract from $24$ instead of hunting for the many that succeed.
Execute — Answer: C
6.EE.A.2 Step 1 Replace the sum with a formula
- The divisor $1 + 2 + \cdots + n$ is an arithmetic sum, which equals $\dfrac{n(n+1)}{2}$.
- So the question asks when $\dfrac{n!}{\,n(n+1)/2\,}$ is a whole number.
- Writing the sum as a single expression in $n$ lets us cancel instead of grinding through $24$ separate divisions.
💡 A running sum from $1$ to $n$ has a closed form, so trade the long addition for one tidy expression.
6.EE.A.3 Step 2 Simplify the quotient
- Divide $n!$ by $\dfrac{n(n+1)}{2}$: dividing by a fraction flips it, giving $\dfrac{2 \cdot n!}{n(n+1)}$.
- Since $n! = n \cdot (n-1)!$, the $n$ cancels, leaving $\dfrac{2\,(n-1)!}{\,n+1\,}$.
- So $n!$ is divisible by the sum exactly when $n+1$ divides $2\,(n-1)!$.
- The whole problem now hangs on the single number $n+1$.
💡 Cancel the shared factor $n$ so only $n+1$ is left to worry about.
7.NS.A.2 Step 3 See when it fails: n+1 an odd prime
- Suppose $n+1$ is an odd prime $p$.
- Then $p$ shares no factor with $2$, and every number in $(n-1)! = 1 \cdot 2 \cdots (p-2)$ is smaller than $p$, so a prime $p$ cannot divide that product either.
- With $p$ dividing neither $2$ nor $(n-1)!$, it cannot divide $2\,(n-1)!$, so the quotient is not a whole number.
- Testing small cases confirms the pattern: $n+1 = 3, 5, 7$ (that is $n = 2, 4, 6$) all fail.
💡 A prime can only come from a factor equal to itself, and every factor below it is too small.
7.NS.A.2 Step 4 See when it works: everything else
- If $n+1$ is composite and at least $6$, it splits into two different factors $a \ne b$ that are both at most $n-1$, so both already sit inside $(n-1)!$ and their product $n+1$ divides it.
- A prime square like $9$ or $25$ still works because two separate multiples of the prime (for $9$: the $3$ and the $6$) live below $n-1$.
- The tiny leftovers are covered too: $n+1 = 4$ works because $2\,(n-1)! = 2 \cdot 2! = 4$, and $n+1 = 2$ (that is $n = 1$) works since $2 \mid 2 \cdot 0!$.
- So the quotient is a whole number for every $n+1$ that is not an odd prime.
💡 A composite number's factors are already waiting inside the factorial, so it divides in.
4.OA.B.4 Step 5 Count the complement
- Only odd-prime values of $n+1$ fail, so count those and subtract from $24$.
- As $n$ runs from $1$ to $24$, $n+1$ runs from $2$ to $25$.
- The odd primes in that range are $3, 5, 7, 11, 13, 17, 19, 23$ — exactly $8$ of them.
- Every other value of $n$ works, so the count of successes is $24 - 8 = 16$.
- The answer is (C).
💡 Failures are the rare odd primes, so counting them and subtracting beats listing every success.
6.EE.A.2 The divisor $1 + 2 + \cdots + n$ is an arithmetic sum, which equals $\dfrac{n(n+ 6.EE.A.3 Divide $n!$ by $\dfrac{n(n+1)}{2}$: dividing by a fraction flips it, giving $\df 7.NS.A.2 Suppose $n+1$ is an odd prime $p$. Then $p$ shares no factor with $2$, and every 7.NS.A.2 If $n+1$ is composite and at least $6$, it splits into two different factors $a 4.OA.B.4 Only odd-prime values of $n+1$ fail, so count those and subtract from $24$. As $ Review
Reasonableness: The eight failing values of $n$ are $2, 4, 6, 10, 12, 16, 18, 22$ — precisely the $n$ where $n+1$ is an odd prime — and checking any of them by hand agrees: for $n = 4$, the sum is $10$ but $4! = 24$ is not a multiple of $10$. The successes include easy sanity checks like $n = 3$ (sum $6$, and $3! = 6$) and $n = 5$ (sum $15$, and $5! = 120 = 15 \cdot 8$). Since failures are the exception, an answer near the top of the range is expected, and $16$ out of $24$ fits; the far-smaller choices $8$ and $12$ would need far more failures than the handful of odd primes allow.
Alternative: Skip the general argument and just build a table for $n = 1$ to $24$: compute the sum $\frac{n(n+1)}{2}$ and test whether $n!$ is a multiple. The whole-number quotients occur at $n = 1, 3, 5, 7, 8, 9, 11, 13, 14, 15, 17, 19, 20, 21, 23, 24$ — sixteen values — matching (C). The table also makes the pattern jump out: the misses land exactly on $n = 2, 4, 6, 10, 12, 16, 18, 22$, one below each odd prime.
CCSS standards used (min grade 7)
6.EE.A.2Write, read, and evaluate expressions in which letters stand for numbers (Rewriting the running sum $1 + 2 + \cdots + n$ as the single expression $\frac{n(n+1)}{2}$.)6.EE.A.3Apply the properties of operations to generate equivalent expressions (Simplifying the quotient $\frac{n!}{n(n+1)/2}$ to the equivalent form $\frac{2\,(n-1)!}{n+1}$ by cancelling the shared factor $n$.)7.NS.A.2Apply and extend understanding of multiplication and division of rational numbers (Deciding when $n+1$ divides the product $2\,(n-1)!$ — a prime cannot, but a composite's factors already sit inside the factorial.)4.OA.B.4Find all factor pairs and recognize multiples; determine prime or composite (Classifying each $n+1$ as prime or composite and counting the odd primes between $2$ and $25$ to reach $24 - 8 = 16$.)
⭐ Rewrite $1 + 2 + \cdots + n$ as $\frac{n(n+1)}{2}$, simplify, and the divisibility fails only when $n+1$ is an odd prime — so count those $8$ primes and subtract from $24$ to get $16$.
⭐ Rewrite $1 + 2 + \cdots + n$ as $\frac{n(n+1)}{2}$, simplify, and the divisibility fails only when $n+1$ is an odd prime — so count those $8$ primes and subtract from $24$ to get $16$.
More like this
Same archetype — closest grade level first.