Problem:
How many ordered pairs (a,b) of positive integers satisfy the equation
a⋅b+63=20⋅lcm(a,b)+12⋅gcd(a,b)
where gcd(a,b) denotes the greatest common divisor of a and b, and lcm(a,b) denotes their least common multiple?
Answer Choices:
A. 0
B. 2
C. 4
D. 6
E. 8
Solution:
Recall that a⋅b=gcd(a,b)⋅lcm(a,b). Let x=lcm(a,b) and y=gcd(a,b). The given equation is then xy+63=20x+12y, which can be rewritten as
(x−12)(y−20)=240−63=177=3⋅59=1⋅177.
Because x and y are integers, one of the following must be true:
-
x−12=1 and y−20=177,
-
x−12=177 and y−20=1,
-
x−12=3 and y−20=59,
-
x−12=59 and y−20=3.
Therefore (x,y) must be (13,197),(189,21),(15,79), or (71,23). Because x must be a multiple of y, only (x,y)=(189,21) is possible. Therefore gcd(a,b)=21=7⋅3, and lcm(a,b)=189=7⋅33. Both a and b are divisible by 7 but not by 72; one of a and b is divisible by 3 but not 32, and the other is divisible by 33 but not 34; and neither is divisible by any other prime. Therefore one of them is 7⋅3=21 and the other is 7⋅33=189. There are (B)2 ordered pairs, (a,b)=(21,189) and (a,b)=(189,21).
The problems on this page are the property of the MAA's American Mathematics Competitions