AMC 10 · 2024 · #18

Grade 8 number-theory

Archetype Modular Cycle Frequency Count └ Sub-archetype Floor Count Across Residue Bins

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

📏 Long solution 💡 4 insights

Problem

For how many integer bases b with 5 ≤ b ≤ 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.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

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

How to solve

Strategy Identify Subproblems

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³ + 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² ≡ 1 (mod 8) — that single fact collapses the odd case to a linear congruence.

1STEP 1

Subproblem 1: rewrite 2024_b in base ten as 2b³ + 2b + 4, so "divisible by 16" becomes 2b³ + 2b + 4 ≡ 0 (mod 16).

2024_b = 2b³ + 2b + 4, 2b³ + 2b + 4 ≡ 0 (mod 16)

2STEP 2

Subproblem 2: every term is even, so divide the congruence by 2 — it shrinks to the easier b³ + b + 2 ≡ 0 (mod 8).

2(b³ + b + 2) ≡ 0 (mod 16) ⟺ b³ + b + 2 ≡ 0 (mod 8)

3STEP 3

Subproblem 3a (b odd): since b² ≡ 1 (mod 8), the cubic collapses to a linear congruence giving b ≡ 3 (mod 4).

b + b + 2 ≡ 0 (mod 8) → 2(b+1) ≡ 0 (mod 8) → b ≡ 3 (mod 4)

4STEP 4

Subproblem 3b: the odd solutions b ≡ 3 (mod 4) split into b ≡ 3 (mod 8) and b ≡ 7 (mod 8).

{b odd: b ≡ 3 (mod 4)} = {b ≡ 3 (mod 8)} ∪ {b ≡ 7 (mod 8)}

5STEP 5

Subproblem 3c (b even): writing b = 2k kills the cube mod 8, leaving 2k + 2 ≡ 0, so the even solutions are b ≡ 6 (mod 8).

(2k)³ + 2k + 2 ≡ 2k + 2 ≡ 0 (mod 8) → k ≡ 3 (mod 4) → b ≡ 6 (mod 8)

6STEP 6

Combine the cases: b qualifies exactly when b ≡ 3, 6, or 7 (mod 8) — 3 of every 8 consecutive bases.

Valid b (mod 8) ∈ {3, 6, 7}, density =

\frac{3}{8}

7STEP 7

Subproblem 4: [1, 2024] holds 253 blocks × 3 = 759 solutions; only b = 3 falls below 5, so K = 759 - 1 = 758.

K = 253 · 3 - 1 = 759 - 1 = 758

8STEP 8

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

7 + 5 + 8 = 20 → (D)

Answer

Spot-check the residue list with a small base. Take b = 3 (a claimed solution): 2b³ + 2b + 4 = 2(27) + 6 + 4 = 64 = 4 · 16, divisible by 16. Take b = 6: 2(216) + 12 + 4 = 432 + 16 = 448 = 28 · 16, divisible. Take b = 7: 2(343) + 14 + 4 = 686 + 18 = 704 = 44 · 16, divisible. Now a non-solution: b = 5 gives 2(125) + 10 + 4 = 264 = 16 · 16 + 8, not divisible — correct because 5 ≢ 3, 6, 7 (mod 8). The density

\frac{3}{8}

predicts about

\frac{3}{8}

(2020) ≈ 758 solutions in [5, 2024], matching K = 758 exactly. Digit sum 20 is answer (D).

💡Key takeaway

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 $\frac{3}{8}$ of the window, adjusted for the edges.

More like this