AMC 10 · 2020 · #24

Grade 6 number-theory

Archetype Small-Domain Constrained Search └ Sub-archetype Logic-Deduction / Elimination

gcddivisibility-ruleslcmmodular-arithmeticprime-factorizationdigit-sum caseworksystematic-enumerationidentify-subproblems ↑ Prerequisites: gcdprime-factorization

📏 Long solution 💡 3 insights

Problem

Find the smallest positive integer n ＞ 1000 satisfying both gcd(63, n+120) = 21 and gcd(n+63, 120) = 60. Then compute the sum of the digits of that n.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

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

How to solve

Strategy Identify Subproblems

Tool #7 (Subproblems): each GCD condition unpacks into a divisibility AND a non-divisibility — handle them one prime at a time. Tool #5 (Pattern): each condition gives an arithmetic progression {base + (period) k}; intersect the two progressions. Tool #6 (Guess and Check): once we know the candidates form an arithmetic sequence 237, 657, 1077, 1497, 1917, … with period 420, check each n ＞ 1000 in order against the non-divisibility filters. Tool #3 (Eliminate): cleanly rules out j = 2 (fails 9 ∤ ) and j = 3 (fails odd-multiplier).

1STEP 1

Unpack condition 1: gcd(63, n+120) = 21 means 21 ∣ (n+120) yet 9 ∤ (n+120), else the gcd would jump to 63.

21 ∣ (n+120) AND 9 ∤ (n+120)

2STEP 2

Unpack condition 2: gcd(n+63, 120) = 60 means 60 ∣ (n+63) but $\frac{n+63}{60}$ is odd, since the only gap up to 120 is one more factor of 2.

60 ∣ (n+63) AND

\frac{n+63}{60}

is odd

3STEP 3

Translate to congruences: n + 120 ≡ 0 (mod 21) gives n ≡ 6 (mod 21), and 60 ∣ (n+63) gives n ≡ 57 (mod 60).

n ≡ 6 (mod 21), n ≡ 57 (mod 60)

4STEP 4

Substitute n = 60k + 57 into the first congruence and solve: k ≡ 3 (mod 7), so n = 420j + 237 (period 420 = lcm(21, 60)).

n = 420 j + 237 for integer j ≥ 0

5STEP 5

From 420j + 237 ＞ 1000 (so j ≥ 2), the ordered candidates are n = 1077, 1497, 1917, …; apply the two 'no extra factor' filters in turn.

j = 2 → n = 1077; j = 3 → n = 1497; j = 4 → n = 1917

6STEP 6

Test n = 1077: n + 120 = 1197 = 9 · 133, so 9 ∣ 1197 — condition (i) fails (gcd becomes 63). Reject.

\frac{1197}{9}

= 133 → 9 ∣ 1197 (bad)

7STEP 7

Test n = 1497: 9 ∤ 1617 passes, but n + 63 = 1560 and $\frac{1560}{60}$ = 26 is even — condition (ii) fails (gcd becomes 120). Reject.

\frac{n+63}{60}

\frac{1560}{60}

= 26 (even, bad)

8STEP 8

Test n = 1917: 9 ∤ 2037 passes and n + 63 = 1980 with $\frac{1980}{60}$ = 33 odd passes — so n = 1917 clears both gcd conditions.

n = 1917;

\frac{2037}{21}

= 97, 9 ∤ 2037;

\frac{1980}{60}

= 33 odd

9STEP 9

The digit sum of 1917 is 1 + 9 + 1 + 7 = 18, choice (C).

1 + 9 + 1 + 7 = 18 → (C)

Answer

Direct verification: for n = 1917, gcd(63, 2037) = gcd(63, 2037 mod 63) = gcd(63, 21) = 21 ✓ (since 2037 = 32 · 63 + 21); and gcd(1980, 120) = gcd(120, 1980 mod 120) = gcd(120, 60) = 60 ✓. Smaller candidates: n = 1077, 1497 were both ruled out by the side conditions, so 1917 is genuinely the smallest. Digit sum 1+9+1+7 = 18 matches choice (C). Choice (D) 21 is the trap from misreading "gcd = 21" as the answer; (A) 12 is the trap from n = 1497 which fails condition 2.

💡Key takeaway

This AMC 10 problem only needs Grade 6 GCD and divisibility you already know — each GCD condition splits into "divides exactly" plus "no extra factor", giving candidates 1077, 1497, 1917, … in steps of 420; the first two fail one side condition each, so n = 1917 and the digit sum is 1+9+1+7=18.

More like this