Track / Stage 8 / 139 of 180 #1839 of 1964

Problem 1839

IMO Shortlist mid-range; USAMO P2/P5

Number theory Difficulty 8.5 Prove it Selection tests for the Balkan Mathematical Olympiad 2013 · Saudi Arabia · 2013

For positive integers $a$ and $b$ , $\operatorname{gcd}(a, b)$ denotes their greatest common divisor and $\operatorname{lcm}(a, b)$ their least common multiple. Determine the number of ordered pairs $(a, b)$ of positive integers satisfying the equation
$a b+63=20 \operatorname{lcm}(a, b)+12 \operatorname{gcd}(a, b).$

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let $d=\operatorname{gcd}(a, b)$ and $a=d a'$ , $b=d b'$ with $a', b'$ two relatively prime positive integers. The equation becomes
$a' b' d^2 + 63 = 20 a' b' d + 12 d$
Therefore, $d$ divides $63$ and we have
$a' b' d + \frac{63}{d} = 20 a' b' + 12$
If $5 < d < 20$ , then $a' b' d + \frac{63}{d} < 20 a' b' + 12$ , and this is impossible. Hence, $d = 1, 3, 21$ , or $63$ .

1. If $d = 1$ , the equation is equivalent to $51 = 19 a' b'$ , which is impossible since $19$ does not divide $51$ .

2. If $d = 3$ , the equation is equivalent to $9 = 17 a' b'$ , which is impossible since $17$ does not divide $9$ .

3. If $d = 21$ , the equation is equivalent to $a' b' = 9$ . Because $a', b'$ are relatively prime positive integers, either $a' = 1, b' = 9$ or $a' = 9, b' = 1$ . This leads to two solutions $(a, b) = (21, 189)$ and $(a, b) = (189, 21)$ .

4. If $d = 63$ , the equation is equivalent to $43 a' b' = 11$ , which is impossible since $43$ does not divide $11$ .

Therefore, the equation has two solutions $(a, b) = (21, 189)$ and $(a, b) = (189, 21)$ .

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.