AMC 10 · 2024 · #18

Grade 8 number-theory

modular-arithmeticdigit-decompositiondivisibility-rulesparity identify-subproblemscaseworkpattern-recognition ↑ Prerequisites: modular-arithmeticplace-valuedivisibility-rules

📏 Long solution 💡 4 insights

Problem

There are exactly $K$ positive integers $b$ with $5 \leq b \leq 2024$ such that the base- $b$ integer $2024_b$ is divisible by $16$ (where $16$ is in base ten). What is the sum of the digits of $K$ ?

$\textbf{(A) }16\qquad\textbf{(B) }17\qquad\textbf{(C) }18\qquad\textbf{(D) }20\qquad\textbf{(E) }21$

Pick an answer.

(A)

(B)

(C)

(D)

(E)

View mode:

Toolkit + CCSS Solution

Understand

Restated: For how many integer bases $b$ with $5 \le b \le 2024$ is the four-digit base-$b$ number $2024_b$ divisible by $16$? Call that count $K$, then report the sum of the digits of $K$.

Givens: $2024_b$ is a base-$b$ numeral with digits $2,0,2,4$; Base range: $5 \le b \le 2024$ (we need $b > 4$ so the digit $4$ is legal); Divisibility target: $16$ (in base ten); $K$ is the number of valid $b$, and the final answer is the digit sum of $K$; Answer choices: (A) $16$, (B) $17$, (C) $18$, (D) $20$, (E) $21$

Unknowns: $K$ = the count of valid bases $b$; The digit sum of $K$

Understand

Restated: For how many integer bases $b$ with $5 \le b \le 2024$ is the four-digit base-$b$ number $2024_b$ divisible by $16$? Call that count $K$, then report the sum of the digits of $K$.

Plan

Primary tool: #7 Identify Subproblems

Secondary: #9 Solve an Easier Related Problem

The question stacks four jobs on top of each other: (i) translate $2024_b$ into base ten, (ii) turn "divisible by $16$" into a clean congruence on $b$, (iii) count the bases in $[5, 2024]$ that pass that congruence, (iv) take a digit sum. That stacking is the trigger for Tool #7 (Identify Subproblems) — solve each piece on its own, then stitch. Inside step (ii) we use Tool #9 (Solve an Easier Related Problem): every coefficient in $2b^3 + 2b + 4$ is even, so divide the whole congruence by $2$ to drop the modulus from $16$ to $8$. Working mod $8$ is much friendlier because for any odd $b$, $b^2 \equiv 1 \pmod 8$ — that single fact collapses the odd case to a linear congruence.

Execute — Answer: D

#7 Identify Subproblems 5.NBT.A.1 Step 1

Subproblem 1: rewrite $2024_b$ in base ten.
The digits $2, 0, 2, 4$ in base $b$ stand for $2 \cdot b^3 + 0 \cdot b^2 + 2 \cdot b + 4$.
The divisibility condition becomes a congruence mod $16$.

$$2024_b = 2b^3 + 2b + 4, \quad 2b^3 + 2b + 4 \equiv 0 \pmod{16}$$

💡 Place value in base $b$ is the Grade 5 rule "each place is $b$ times the next", extended one variable at a time.

#9 Solve an Easier Related Problem 6.NS.B.4 Step 2

Subproblem 2: shrink the modulus.
Every term on the left is even, so factor out $2$.
Saying $2x \equiv 0 \pmod{16}$ is the same as $x \equiv 0 \pmod 8$.
This is the Tool #9 move — the same problem with a smaller modulus.

$$2(b^3 + b + 2) \equiv 0 \pmod{16} \;\Longleftrightarrow\; b^3 + b + 2 \equiv 0 \pmod 8$$

💡 Pulling a common factor out of every term is the Grade 6 distributive-property trick, applied to a congruence instead of a sum.

#7 Identify Subproblems 8.EE.A.1 Step 3

Subproblem 3a: solve the mod-$8$ congruence when $b$ is odd.
The key fact: for any odd integer $b$, $b^2 \equiv 1 \pmod 8$ (check $1^2, 3^2, 5^2, 7^2 \equiv 1, 1, 1, 1 \pmod 8$).
So $b^3 = b \cdot b^2 \equiv b \pmod 8$, and the congruence simplifies to a linear one in $b$.

$$b + b + 2 \equiv 0 \pmod 8 \;\Rightarrow\; 2(b+1) \equiv 0 \pmod 8 \;\Rightarrow\; b \equiv 3 \pmod 4$$

💡 "Odd squares are $1$ mod $8$" is one of the most useful integer-exponent facts in number theory — it turns the cubic into a linear congruence.

#7 Identify Subproblems 4.OA.C.5 Step 4

Subproblem 3b: among odd $b$, list those with $b \equiv 3 \pmod 4$.
Such odd $b$ are $3, 7, 11, 15, 19, 23, \dots$ — they alternate between $\equiv 3 \pmod 8$ and $\equiv 7 \pmod 8$.
So the odd solutions are exactly $b \equiv 3 \pmod 8$ and $b \equiv 7 \pmod 8$.

$$\{b \;\text{odd}: b \equiv 3 \pmod 4\} = \{b \equiv 3 \pmod 8\} \cup \{b \equiv 7 \pmod 8\}$$

💡 Going from "step by $4$" to "step by $8$" splits each residue class in two — the Grade 4 "continue a pattern" rule applied to residues.

#7 Identify Subproblems 8.EE.A.1 Step 5

Subproblem 3c: solve the congruence when $b$ is even.
Write $b = 2k$.
Then $b^3 = 8k^3$ vanishes mod $8$, and the congruence collapses to $2k + 2 \equiv 0 \pmod 8$, i.e.
$k \equiv 3 \pmod 4$.
Substituting back, $b = 2k = 8m + 6$.
So the even solutions are exactly $b \equiv 6 \pmod 8$.

$$(2k)^3 + 2k + 2 \equiv 2k + 2 \equiv 0 \pmod 8 \;\Rightarrow\; k \equiv 3 \pmod 4 \;\Rightarrow\; b \equiv 6 \pmod 8$$

💡 Substituting $b = 2k$ kills the cubic term because $(2k)^3$ is already a multiple of $8$ — a clean cube-power fact.

#7 Identify Subproblems 4.OA.C.5 Step 6

Combine the three residue classes: $b$ works iff $b \equiv 3, 6, \text{ or } 7 \pmod 8$.
In every block of $8$ consecutive integers, exactly $3$ of the $8$ residues are good.

$$\text{Valid } b \pmod 8 \;\in\; \{3, 6, 7\}, \quad \text{density } = \dfrac{3}{8}$$

💡 Residues mod $8$ repeat every $8$ steps — once you know which residues qualify, counting is just "how many full blocks fit, plus leftovers".

#7 Identify Subproblems 4.OA.C.5 Step 7

Subproblem 4: count valid $b$ in $[5, 2024]$.
The window $[1, 2024]$ holds exactly $2024 / 8 = 253$ full blocks, giving $253 \times 3 = 759$ solutions.
Now subtract solutions with $b < 5$.
Check $b = 1, 2, 3, 4$ against the residue set $\{3, 6, 7\}$: only $b = 3$ qualifies.
So $K = 759 - 1 = 758$.

$$K = 253 \cdot 3 - 1 = 759 - 1 = 758$$

💡 The "count in a window" trick is to count an easy super-window then subtract the part you do not want.

#7 Identify Subproblems 5.NBT.A.1 Step 8

Final subproblem: take the digit sum of $K = 758$.

$$7 + 5 + 8 = 20 \;\Rightarrow\; \textbf{(D)}$$

💡 Digit sum is base-$10$ place value at its most direct — add the digits and stop.

[1] #7 5.NBT.A.1 Subproblem 1: rewrite $2024_b$ in base ten. The digits $2, 0, 2, 4$ in base $b$

[2] #9 6.NS.B.4 Subproblem 2: shrink the modulus. Every term on the left is even, so factor out

[3] #7 8.EE.A.1 Subproblem 3a: solve the mod-$8$ congruence when $b$ is odd. The key fact: for a

[4] #7 4.OA.C.5 Subproblem 3b: among odd $b$, list those with $b \equiv 3 \pmod 4$. Such odd $b$

[5] #7 8.EE.A.1 Subproblem 3c: solve the congruence when $b$ is even. Write $b = 2k$. Then $b^3

[6] #7 4.OA.C.5 Combine the three residue classes: $b$ works iff $b \equiv 3, 6, \text{ or } 7 \

[7] #7 4.OA.C.5 Subproblem 4: count valid $b$ in $[5, 2024]$. The window $[1, 2024]$ holds exact

[8] #7 5.NBT.A.1 Final subproblem: take the digit sum of $K = 758$.

Review

Reasonableness: Spot-check the residue list with a small base. Take $b = 3$ (a claimed solution): $2b^3 + 2b + 4 = 2(27) + 6 + 4 = 64 = 4 \cdot 16$, divisible by $16$. Take $b = 6$: $2(216) + 12 + 4 = 432 + 16 = 448 = 28 \cdot 16$, divisible. Take $b = 7$: $2(343) + 14 + 4 = 686 + 18 = 704 = 44 \cdot 16$, divisible. Now a non-solution: $b = 5$ gives $2(125) + 10 + 4 = 264 = 16 \cdot 16 + 8$, not divisible — correct because $5 \not\equiv 3, 6, 7 \pmod 8$. The density $\tfrac{3}{8}$ predicts about $\tfrac{3}{8}(2020) \approx 758$ solutions in $[5, 2024]$, matching $K = 758$ exactly. Digit sum $20$ is answer (D).

Alternative: Tool #5 (Look for a Pattern): instead of the algebraic case-split, just compute $2b^3 + 2b + 4 \pmod {16}$ for $b = 1, 2, \dots, 16$ and tabulate which $b$ give $0$. The residues that work are exactly $b \equiv 3, 6, 7 \pmod 8$ — read straight off the table without ever invoking "odd squares are $1$ mod $8$". Then count $\tfrac{3}{8}$ of $[1, 2024]$ minus the one early hit at $b = 3$, same as before.

CCSS standards used (min grade 8)

5.NBT.A.1 Recognize that in a multi-digit number, a digit in one place represents 10 times as much as it represents in the place to its right (Generalizing base-$10$ place value to base $b$ to write $2024_b = 2b^3 + 0 \cdot b^2 + 2b + 4$, and to read the digit sum of $K = 758$.)
6.NS.B.4 Find the greatest common factor and least common multiple; apply the distributive property to express a sum as a product (Pulling the common factor $2$ out of $2b^3 + 2b + 4$ so that $\equiv 0 \pmod{16}$ becomes $b^3 + b + 2 \equiv 0 \pmod 8$ — a smaller, friendlier modulus.)
4.OA.C.5 Generate a number or shape pattern that follows a given rule (Treating residues mod $8$ as a repeating length-$8$ pattern: $3$ of every $8$ consecutive bases qualify, so the count in $[1, 2024]$ is $253 \times 3 = 759$.)
8.EE.A.1 Know and apply the properties of integer exponents (Using $b^2 \equiv 1 \pmod 8$ for odd $b$ (so $b^3 \equiv b \pmod 8$), and using $(2k)^3 = 8k^3 \equiv 0 \pmod 8$ for even $b$ — the two facts that crack the cubic congruence.)

⭐ When divisibility hides inside a polynomial in $b$, split the work: translate the base-$b$ number, shrink the modulus by pulling out common factors, then handle odd $b$ and even $b$ separately. Once you know which residues mod $8$ qualify, counting bases in a long range is just $\tfrac{3}{8}$ of the window, adjusted for the edges.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: D

Review

CCSS standards used (min grade 8)

More like this