Library / /13 of 13

, 2013

Number theory Difficulty 8.5 Shortlist Prove it Saudi Arabia

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).$

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)$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

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