AMC 10 · 2020 · #24

Grade 6 number-theory

Archetype Small-Domain Constrained Search

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

📏 Long solution 💡 3 insights

Problem

Let $n$ be the least positive integer greater than $1000$ for which

$\gcd(63, n+120) =21\quad \text{and} \quad \gcd(n+63, 120)=60.$

What is the sum of the digits of $n$ ?

$\textbf{(A) } 12 \qquad\textbf{(B) } 15 \qquad\textbf{(C) } 18 \qquad\textbf{(D) } 21\qquad\textbf{(E) } 24$

Pick an answer.

(A)

(B)

(C)

(D)

(E)

View mode:

Toolkit + CCSS Solution

Understand

Restated: 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$.

Givens: $63 = 9 \cdot 7 = 3^2 \cdot 7$; $120 = 8 \cdot 15 = 2^3 \cdot 3 \cdot 5$; First condition: $\gcd(63, n+120) = 21$; Second condition: $\gcd(n+63, 120) = 60$; $n > 1000$; want the smallest such $n$ and then its digit sum; Answer choices: (A) $12$, (B) $15$, (C) $18$, (D) $21$, (E) $24$

Unknowns: Smallest valid $n > 1000$ and its digit sum

Understand

Restated: 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$.

Plan

Primary tool: #7 Identify Subproblems

Secondary: #5 Look for a Pattern, #6 Guess and Check, #3 Eliminate Possibilities

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 $\{\text{base} + (\text{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, \ldots$ with period $420$, check each $n > 1000$ in order against the non-divisibility filters. Tool #3 (Eliminate): cleanly rules out $j = 2$ (fails $9 \nmid$) and $j = 3$ (fails odd-multiplier).

Execute — Answer: C

#7 Identify Subproblems 6.NS.B.4 Step 1

Unpack condition 1.
$\gcd(63, n+120) = 21$ means two things at once: (i) $21$ divides $n+120$ — i.e.
$n + 120$ is a multiple of $21$; (ii) the only $63$-factor missing from $n+120$ is the extra $3$ — i.e.
$9 \nmid (n+120)$, otherwise $\gcd$ would become $63$.
So we need $n + 120 \equiv 0 \pmod{21}$ AND $n + 120 \not\equiv 0 \pmod 9$.
The first part is the divisibility; the second is a sanity filter we apply at the end.

$$21 \mid (n+120) \;\text{ AND }\; 9 \nmid (n+120)$$

💡 $\gcd = 21$ packs a YES (divisible by $21$) and a NO (not divisible by $63$, i.e. extra $3$ missing).

#7 Identify Subproblems 6.NS.B.4 Step 2

Unpack condition 2.
$\gcd(n+63, 120) = 60$ requires: (i) $60 \mid (n+63)$; (ii) $120 \nmid (n+63)$, equivalently $(n+63)/60$ is odd (since $120 = 2 \cdot 60$).
The other primes $3, 5$ already saturate via the $60$-factor, so the only "extra" obstruction is the second factor of $2$.

$$60 \mid (n+63) \;\text{ AND }\; (n+63)/60 \text{ is odd}$$

💡 $\gcd = 60$ vs. $120$ hinges on a single factor of $2$ — easy to track.

#5 Look for a Pattern 6.EE.B.7 Step 3

Translate to congruences.
$n + 120 \equiv 0 \pmod{21}$ becomes $n \equiv -120 \equiv -120 + 6 \cdot 21 \equiv 6 \pmod{21}$ (since $6 \cdot 21 = 126$).
And $60 \mid (n+63)$ becomes $n \equiv -63 \equiv -63 + 2 \cdot 60 \equiv 57 \pmod{60}$.

$$n \equiv 6 \pmod{21}, \;\; n \equiv 57 \pmod{60}$$

💡 Two clean congruences capture the divisibility conditions.

#5 Look for a Pattern 6.EE.B.7 Step 4

Combine the two congruences.
From the second, $n = 60k + 57$.
Substitute into the first: $60k + 57 \equiv 6 \pmod{21}$.
Reduce: $60 \equiv 60 - 2 \cdot 21 = 18 \pmod{21}$ and $57 \equiv 57 - 2 \cdot 21 = 15 \pmod{21}$.
So $18k + 15 \equiv 6 \pmod{21}$, i.e.
$18k \equiv -9 \equiv 12 \pmod{21}$.
Divide everything by $\gcd(18, 21) = 3$ (note $3 \mid 12$, so the equation is consistent): $6k \equiv 4 \pmod 7$.
Since $6 \equiv -1 \pmod 7$, this is $-k \equiv 4$, so $k \equiv -4 \equiv 3 \pmod 7$.
Thus $k = 7j + 3$ and $n = 60(7j+3) + 57 = 420 j + 237$.

$$n = 420 j + 237 \;\text{ for integer } j \ge 0$$

💡 Substituting one congruence into the other reveals the period $420 = \mathrm{lcm}(21, 60)$.

#6 Guess and Check 4.OA.A.3 Step 5

Find candidates $> 1000$.
From $420 j + 237 > 1000$, $j > 763/420 \approx 1.81$.
The candidate list is $n = 1077\;(j=2), 1497\;(j=3), 1917\;(j=4), 2337\;(j=5), \ldots$.
Apply the two non-divisibility filters in order.

$$j = 2 \Rightarrow n = 1077; \;\; j = 3 \Rightarrow n = 1497; \;\; j = 4 \Rightarrow n = 1917$$

💡 List the small candidates in order and test the side conditions one by one.

#3 Eliminate Possibilities 6.NS.B.2 Step 6

Test $j=2 \Rightarrow n = 1077$.
Check $9 \nmid (n + 120) = 1197$.
$1197 = 9 \cdot 133$, so $9 \mid 1197$ — condition (i) fails (gives $\gcd(63, 1197) = 63$, not $21$).
Reject.

$$1197 / 9 = 133 \Rightarrow 9 \mid 1197 \;\text{ (bad)}$$

💡 $1+1+9+7 = 18$ is a multiple of $9$ — fast digit-sum check rules $n=1077$ out.

#3 Eliminate Possibilities 6.NS.B.2 Step 7

Test $j=3 \Rightarrow n = 1497$.
Check $9 \nmid (n+120) = 1617$.
Digit sum $1+6+1+7 = 15$, not a multiple of $9$ — passes.
Check $(n+63)/60$ is odd.
$n + 63 = 1560$, $1560 / 60 = 26$, which is even — condition (ii) fails ($\gcd(1560, 120) = 120$, not $60$).
Reject.

$$(n+63)/60 = 1560/60 = 26 \;\text{ (even, bad)}$$

💡 $60$ divides $1560$ "once too many" — the quotient is even, so $120$ divides too.

#6 Guess and Check 6.NS.B.2 Step 8

Test $j=4 \Rightarrow n = 1917$.
Check $9 \nmid (n+120) = 2037$.
Digit sum $2+0+3+7 = 12$, not divisible by $9$ — passes.
Check $(n+63)/60$ is odd.
$n+63 = 1980$, $1980/60 = 33$, which is odd — passes.
So $n = 1917$ satisfies both original $\gcd$ conditions.

$$n = 1917; \;\; 2037/21 = 97, \;\; 9 \nmid 2037; \;\; 1980/60 = 33 \text{ odd}$$

💡 The first candidate that passes both side conditions — minimum found.

#6 Guess and Check 4.OA.A.3 Step 9

Final answer is the digit sum of $1917$: $1 + 9 + 1 + 7 = 18$, choice (C).

$$1 + 9 + 1 + 7 = 18 \Rightarrow \textbf{(C)}$$

💡 Simple addition of the four digits.

[1] #7 6.NS.B.4 Unpack condition 1. $\gcd(63, n+120) = 21$ means two things at once: (i) $21$ di

[2] #7 6.NS.B.4 Unpack condition 2. $\gcd(n+63, 120) = 60$ requires: (i) $60 \mid (n+63)$; (ii)

[3] #5 6.EE.B.7 Translate to congruences. $n + 120 \equiv 0 \pmod{21}$ becomes $n \equiv -120 \e

[4] #5 6.EE.B.7 Combine the two congruences. From the second, $n = 60k + 57$. Substitute into th

[5] #6 4.OA.A.3 Find candidates $> 1000$. From $420 j + 237 > 1000$, $j > 763/420 \approx 1.81$.

[6] #3 6.NS.B.2 Test $j=2 \Rightarrow n = 1077$. Check $9 \nmid (n + 120) = 1197$. $1197 = 9 \cd

[7] #3 6.NS.B.2 Test $j=3 \Rightarrow n = 1497$. Check $9 \nmid (n+120) = 1617$. Digit sum $1+6+

[8] #6 6.NS.B.2 Test $j=4 \Rightarrow n = 1917$. Check $9 \nmid (n+120) = 2037$. Digit sum $2+0+

[9] #6 4.OA.A.3 Final answer is the digit sum of $1917$: $1 + 9 + 1 + 7 = 18$, choice (C).

Review

Reasonableness: Direct verification: for $n = 1917$, $\gcd(63, 2037) = \gcd(63, 2037 \bmod 63) = \gcd(63, 21) = 21$ ✓ (since $2037 = 32 \cdot 63 + 21$); and $\gcd(1980, 120) = \gcd(120, 1980 \bmod 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.

Alternative: Tool #6 (Guess and Check) by hand: start at $n = 1001$ and step up looking first for $n + 63 \equiv 60 \pmod{120}$ (i.e. $n \equiv 57 \pmod{60}$ with odd quotient), giving $n \in \{1077, 1197, 1317, \ldots\}$ (period $120$, alternating odd/even quotients keeps half), and then filter by $n + 120 \equiv 21 \pmod{63}$ (i.e. $n + 120$ divisible by $21$ but not $63$). The cross-test arrives at $1917$ directly.

CCSS standards used (min grade 6)

4.OA.A.3 Solve multi-step word problems using four operations with whole numbers (Building the arithmetic sequence $420 j + 237$ and adding the four digits of $1917$.)
6.NS.B.2 Fluently divide multi-digit numbers using the standard algorithm (Computing $2037/21, 1980/60, 1197/9$, and similar quotients to test divisibility filters.)
6.NS.B.4 Find greatest common factor and least common multiple of two numbers (Unpacking each $\gcd$ condition into a divisibility plus a non-divisibility filter, and using $\mathrm{lcm}(21, 60) = 420$.)
6.EE.B.7 Solve real-world problems by writing and solving equations of the form px = q (Translating divisibility into linear congruences and combining $n \equiv 6 \pmod{21}$ with $n \equiv 57 \pmod{60}$ into $n = 420j + 237$.)

⭐ 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, \ldots$ 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$.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: C

Review

CCSS standards used (min grade 6)

More like this