AMC 10 · 2018 · #23

Grade 7 number-theory

Archetype Small-Domain Constrained Search └ Sub-archetype Factor-Pair Enumeration

gcdlcmsimons-favorite-factoring-trick convert-to-algebrasimons-favorite-factoring-tricksystematic-enumeration ↑ Prerequisites: gcdlcm

📏 Medium solution 💡 3 insights

Problem

Count the ordered pairs (a,b) of positive integers that make a· b + 63 = 20 lcm(a,b) + 12 gcd(a,b) true. "Ordered" means (a,b) and (b,a) are counted separately when a ≠ b.

Pick an answer.

(A)

$text{ 0}$

(B)

$text{ 2}$

(C)

$text{ 4}$

(D)

$text{ 6}$

(E)

$text{ 8}$

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

How to solve

Strategy Convert to Algebra

Tool #4 (Introduce a Variable): name the two messy quantities g=gcd(a,b) and l=lcm(a,b) so the equation stops being about a and b directly. Tool #13 (Convert to Algebra): the identity ab=g l rewrites the whole thing as one clean equation in g and l, which Simon's Favorite Factoring Trick turns into a product (g-20)(l-12)=177. Tool #2 (Make a Systematic List): 177 has only a handful of divisors, so every candidate (g,l) can be listed in full. Tool #3 (Eliminate Possibilities): the structural rule that a gcd must divide its lcm throws out all but one candidate, after which counting the actual pairs is quick.

1STEP 1

Rename gcd and lcm as g and l

Set g=gcd(a,b), l=lcm(a,b); since ab=g·l, the number-theory equation becomes a clean one in g and l: gl+63=20l+12g.

ab=g l → g l+63=20 l+12 g

2STEP 2

Factor with Simon's Trick

Move all to one side and add 240; Simon's Favorite Factoring Trick then gives (g-20)(l-12)=177.

(g-20)(l-12)=177

3STEP 3

List the factor pairs of 177

177=3×59 has four positive factor pairs, giving candidates (g,l)=(21,189),(23,71),(79,15),(197,13); negative pairs are impossible.

(g-20, l-12)∈{(1,177),(3,59),(59,3),(177,1)}

4STEP 4

Keep only pairs where g divides l

A gcd must divide its lcm; only (g,l)=(21,189) passes since 189=21·9, while 23 ∤ 71, 79 ∤ 15, 197 ∤ 13 all fail.

21 ∣ 189 ✓, 23 ∤ 71, 79 ∤ 15, 197 ∤ 13

5STEP 5

Count the ordered pairs from g=21, l=189

With a=gx, b=gy, gcd(x,y)=1: xy=189/21=9, so (x,y)=(1,9),(9,1) — not (3,3) — giving 2 ordered pairs, (21,189) and (189,21).

xy=189/21=9, gcd(x,y)=1 → (x,y)=(1,9),(9,1) → 2 pairs

Answer

text{ 2}

Check the surviving pair in the original equation. For (a,b)=(21,189): gcd=21, lcm=189, and ab=3969. Left side =3969+63=4032; right side =20·189+12·21=3780+252=4032. They match, and by symmetry (189,21) works too. No other (g,l) passed the divisibility test, so exactly 2 pairs exist. The count being even makes sense because unequal solutions come in mirrored twos, consistent with choice (B).

💡Key takeaway

Rename the gcd and lcm, use that their product is ab, factor with Simon's trick, and only the factor pair where the gcd divides the lcm survives, giving 2 ordered pairs.

Rename gcd and lcm as g and l
Factor with Simon's Trick
List the factor pairs of 177
Keep only pairs where g divides l
Count the ordered pairs from g=21, l=189

Rename gcd and lcm as g and l

Factor with Simon's Trick

List the factor pairs of 177

Keep only pairs where g divides l

Count the ordered pairs from g=21, l=189

More like this