AMC 10 · 2021 · #16

Grade 6 number-theory

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

gcdparitycaseworkprime-numbers caseworkbound-inequality-then-enumerate ↑ Prerequisites: gcd

📏 Long solution 💡 4 insights

Problem

Three positive whole numbers add up to 23. Their three pairwise greatest common divisors add up to 9. More than one triple can satisfy both, and each produces its own sum of squares. Find every reachable sum of squares, counting repeats once, and add the survivors together.

Pick an answer.

(A)

259

(B)

438

(C)

516

(D)

625

(E)

687

How to solve

Strategy Eliminate Possibilities

Searching over a, b, c directly is the wrong end of the problem — hundreds of triples, and the gcd condition is awkward to test. The fix is to search over the gcds instead. Tool #4 (Introduce a Variable) names them x, y, z, and now the second condition is the clean equation x+y+z=9 with small positive parts. Tool #2 (Make a Systematic List) writes down every way three odd numbers can total 9 — there are only three. Then Tool #3 (Eliminate Possibilities) does the heavy lifting twice: a parity argument kills an entire branch of the problem in one line, and a divisibility argument built on the primality of 23 kills one of the three remaining shapes. Only two survive, and Tool #7 (Identify Subproblems) turns each one into a short, self-contained hunt for the actual triple.

1STEP 1

Name the three gcds

Name the three gcds.

x = gcd(a,b), y = gcd(b,c), z = gcd(c,a), x + y + z = 9, 1 ≤ x, y, z ≤ 7

2STEP 2

An odd total forces all three odd

An odd total forces all three odd.

b, c even → y even; a odd → x, z odd → x + y + z ≡ 1 + 0 + 1 ≡ 0 (mod 2), but 9 is odd

3STEP 3

Three shapes for the gcds

Only three shapes are possible.

{x, y, z} = {1, 1, 7}, {1, 3, 5}, or {3, 3, 3}

4STEP 4

The prime 23 kills 3, 3, 3

Because 23 is prime, one shape dies.

p ∣ x and p ∣ y → p ∣ a, b, c → p ∣ a+b+c = 23 → p = 23 ＞ 7 contradiction

5STEP 5

Shape 1, 1, 7 gives 7, 7, 9

The first shape gives one triple.

7 ∣ a, 7 ∣ b, a + b ≤ 22 → a = b = 7, c = 9 gcd(7,7) + gcd(7,9) + gcd(9,7) = 7 + 1 + 1 = 9 ✓

6STEP 6

Shape 1, 3, 5 gives 3, 5, 15

The second gives another.

5 ∣ b and 3 ∣ b → 15 ∣ b, b ≤ 21 → b = 15 a + c = 8, 5 ∣ a, 3 ∣ c → a = 5, c = 3 gcd(5,15) + gcd(15,3) + gcd(3,5) = 5 + 3 + 1 = 9 ✓

7STEP 7

Add the two distinct values

Adding the two values gives 438.

7² + 7² + 9² = 49 + 49 + 81 = 179 3² + 5² + 15² = 9 + 25 + 225 = 259 179 + 259 = 438 → (B)

Answer

438

First, a size check that catches the main trap. For positive integers with a+b+c=23, the quantity a²+b²+c² is smallest when the numbers are as even as possible, 8²+8²+7² = 177, and largest when they are as lopsided as possible, 21²+1²+1² = 443. So any single value of a²+b²+c² lies between 177 and 443. That range immediately shows (C) 516, (D) 625 and (E) 687 are too large to be single values, while (A) 259 sits comfortably inside — which is exactly why (A) is the trap: it is the value from {3,5,15} alone, chosen by a solver who found one triple and stopped before hunting for the second. It is also a good sign that 179 lands just above the minimum 177, since {7,7,9} is nearly balanced, and that 259 sits higher, since {3,5,15} is more lopsided. Second, an exhaustiveness check. The elimination never guessed: three odd numbers can total 9 in only three ways, one of those was ruled out by the primality of 23, and inside each surviving shape the divisibility plus the bound a+b+c=23 left no freedom at all. Both surviving triples were verified directly against the original conditions, so 179 and 259 are genuine and nothing else can appear.

💡Key takeaway

Check parity first: because the three gcds add to an odd 9, all of a, b, c must be odd, and that single fact shrinks a search over hundreds of triples down to three cases you can finish by hand.

Name the three gcds
An odd total forces all three odd
Three shapes for the gcds
The prime 23 kills 3, 3, 3
Shape 1, 1, 7 gives 7, 7, 9
Shape 1, 3, 5 gives 3, 5, 15
Add the two distinct values