2018 AMC 10B Problem 23

Problem 23 of 25HarderAlgebra Number Theory

How many ordered pairs

(a, b)

of positive integers satisfy the equation

\begin{aligned} a \cdot b + 63 &= 20 \cdot \operatorname{lcm}(a, b) \\ &\quad {}+ 12 \cdot \gcd(a, b), \end{aligned}

where

\gcd(a, b)

denotes the greatest common divisor of

a

and

b,

and

\operatorname{lcm}(a, b)

denotes their least common multiple?

Show solution

Solution

Recall

ab=\gcd(a,b)\operatorname{lcm}(a,b).

Let

x=\operatorname{lcm}(a,b)

and

y=\gcd(a,b).

The equation becomes

(x-12)(y-20)=177=3\cdot59.

The positive factor pairs give

(x,y)=(13,197),

(189,21),

(15,79),

and

(71,23).

The negative factor pairs make either

x

or

y

negative, so they are impossible. Also

y

must divide

x,

and only

(x,y)=(189,21)

passes. Write

a=21u

and

b=21v.

Then

\gcd(u,v)=1

and

uv=\frac{189}{21}=9,

so

(u,v)=(1,9)

or

(9,1).

Hence the two ordered pairs are

(21,189)

and

(189,21),

and B is the correct answer.

More practice

Concepts: least common multiple · greatest common divisor · Simon’s Favorite Factoring Trick

Problem text and solution from the LIVE past-contest archive. See also the AoPS wiki page for community solutions.