AMC 10 · 2018 · #22

Grade 6 number-theory

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

gcdprime-factorizationdivisibility-rules caseworkbound-inequality-then-enumerate ↑ Prerequisites: gcdprime-factorization

📏 Long solution 💡 3 insights

Problem

Positive integers a,b,c,d satisfy gcd(a,b)=24, gcd(b,c)=36, gcd(c,d)=54, and 70 ＜ gcd(d,a) ＜ 100. From the five choices 5,7,11,13,17, decide which one is forced to divide a.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

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

How to solve

Strategy Introduce a Variable

A gcd works one prime at a time: it keeps the smaller exponent of that prime found in the two numbers. So Tool #4 (Introduce a Variable): let e_p(x) stand for the exponent of prime p in x, turning every gcd fact into a plain statement about smaller-of-two exponents. Tool #7 (Identify Subproblems): handle the prime 2 and the prime 3 separately, since they never interact, and pin down the exact powers of 2 and 3 in a. That fixes gcd(d,a) to be 6 times a number sharing no factor of 2 or 3. Tool #3 (Eliminate Possibilities): only one multiple of 6 in the window 70 ＜ x ＜ 100 survives that restriction, which reveals the prime forced into a.

1STEP 1

Factor and name the exponents

Only the primes 2 and 3 appear. Introduce e_p(x) for p's exponent, since the key rule is that gcd keeps each prime's smaller exponent.

24=2³·3, 36=2²·3², 54=2·3³

2STEP 2

Write the smaller-exponent rules

The smaller exponent turns four gcds into six min-equations: for prime 2 the mins are 3, 2, 1, for prime 3 they are 1, 2, 3.

min(e₂(a),e₂(b))=3, min(e₂(b),e₂(c))=2, min(e₂(c),e₂(d))=1

3STEP 3

Track the powers of 2

With e₂(b) ≥ 3 we get e₂(c)=2, then e₂(d)=1, while a keeps e₂(a) ≥ 3.

e₂(b) ≥ 3→ e₂(c)=2→ e₂(d)=1, e₂(a) ≥ 3

4STEP 4

Track the powers of 3

Symmetrically, e₃(b) ≥ 2 forces e₃(a)=1, while min(e₃(c),e₃(d))=3 gives e₃(d) ≥ 3: a holds exactly one 3.

e₃(b) ≥ 2→ e₃(a)=1, e₃(d) ≥ 3

5STEP 5

Build gcd(d, a)

Comparing d and a: min for 2 is min(1, ≥ 3)=1, for 3 is min( ≥ 3,1)=1, so gcd(d,a)=6m where m shares no factor of 2 or 3.

gcd(d,a)=2¹·3¹· m=6m, gcd(m,6)=1

6STEP 6

Use the window to pin the value

70 ＜ 6m ＜ 100 leaves m∈{12,…,16}; dropping even and multiples of 3 gives m=13, so gcd(d,a)=78 divides a: 13 ∣ a, choice (D).

70 ＜ 6m ＜ 100→ m=13→ gcd(d,a)=78→ 13 ∣ a

Answer

The forced value gcd(d,a)=78=2·3·13 does sit strictly between 70 and 100, and 78 divides a, so 13 ∣ a. A concrete build confirms it is possible: take a=2³·3·13=312, b=2³·3²=72, c=2²·3³=108, d=2·3³·13=702. Then gcd(a,b)=24, gcd(b,c)=36, gcd(c,d)=54, and gcd(d,a)=78, all matching. The other choices are not forced: nothing in the conditions requires a to carry 5, 7, 11, or 17.

💡Key takeaway

A gcd keeps the smaller power of each prime, so track 2s and 3s separately: that forces gcd(d,a)=6m, and 78=6·13 is the only fit between 70 and 100, so 13 must divide a — choice (D).

Factor and name the exponents
Write the smaller-exponent rules
Track the powers of 2
Track the powers of 3
Build gcd(d, a)
Use the window to pin the value