AMC 10 · 2023 · #18

Grade 8 number-theory

gcdprime-factorizationdivisibility-ruleslogical-deduction caseworkconvert-to-algebralogical-deduction ↑ Prerequisites: gcdprime-factorization

📏 Long solution 💡 3 insights

Problem

Positive integers a, b, c satisfy a/14 + b/15 = c/210. Decide which of the three statements I, II, III about gcd(a,14), gcd(b,15), gcd(c,210) are necessarily true, and pick the choice naming exactly that set.

Pick an answer.

(A)

$~\text{I, II, and III}$

(B)

$~\text{I only}$

(C)

$~\text{I and II only}$

(D)

$~\text{III only}$

(E)

$~\text{II and III only}$

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

How to solve

Strategy Identify Subproblems

Three independent yes/no questions live in one problem — perfect setup for Tool #7 (Identify Subproblems). Clear denominators first: multiplying by 210 gives c = 15a + 14b. Then test each statement separately. Tool #3 (Eliminate Possibilities) supplies a single counterexample to kill Statement I. Tool #13 (Convert to Algebra) — specifically modular reduction mod 2, 3, 5, 7 — settles Statement III, and Statement II follows immediately because "and" implies "or".

1STEP 1

Clear denominators: the LCM of 14, 15, 210 is 210, so multiplying through gives c = 15a + 14b.

210·a/14 + 210·b/15 = 210·c/210 ⟹ c = 15a + 14b

2STEP 2

Counterexample to I: a=1 (so gcd(a,14)=1), b=3 gives c=57=3·19, so gcd(57,210)=3≠1 — Statement I is false.

a=1, b=3 → c=57, gcd(57,210)=3

3STEP 3

Forward III: if gcd(a,14)=1 and gcd(b,15)=1, then mod 2,7 give c≡a, mod 3,5 give c≡2b,4b — never 0, so gcd(c,210)=1.

c ≢ 0 (mod 2,3,5,7) ⟹ gcd(c,210)=1

4STEP 4

Reverse III: using gcd(x+ky,y)=gcd(x,y), gcd(c,14)=gcd(a,14) and gcd(c,15)=gcd(b,15), so gcd(c,210)=1 forces both to be 1.

gcd(c,14)=gcd(a,14), gcd(c,15)=gcd(b,15)

5STEP 5

Statement II wants only the weaker 'or', which III's reverse 'and' already gives — so II is true; with I false, II and III are the answer.

(II AND III true, I false) → (E) II and III only

Answer

~II and III only

Cross-check Statement III on a clean example: a=1, b=1 gives c = 15 + 14 = 29 — prime, so gcd(29, 210) = 1, matching gcd(1, 14) = gcd(1, 15) = 1. Cross-check the reverse: any c coprime to 210 comes from (a, b) where a is coprime to 14 and b to 15. Counterexample to I: a=1, b=3 gives c = 57, gcd(57, 210) = 3 ≠ 1 despite gcd(1, 14)=1. So I is false, III is true (both directions), II is true (weaker than III's reverse). The right choice is (E) II and III only.

💡Key takeaway

Multiplying through by 210 turns the equation into c = 15a + 14b. Mod each prime in {2, 3, 5, 7}, one of the two terms vanishes, so gcd(c, 210) = 1 is equivalent to gcd(a, 14) = gcd(b, 15) = 1 (Statement III). That "and" automatically implies the "or" in Statement II, but Statement I fails because a = 1, b = 3 gives c = 57 — divisible by 3. Answer: (E) II and III only.