Maths Olympiad Prep

Library / /225 of 348

Number theory Difficulty 5.0 AIME Find the answer

Suppose aa and bb be positive integers not exceeding 100 such that ab=(lcm(a,b)gcd(a,b))2a b=\left(\frac{\operatorname{lcm}(a, b)}{\operatorname{gcd}(a, b)}\right)^{2} Compute the largest possible value of a+ba+b.

A number or a short expression. Spacing and $ signs are ignored.

Solution

For any prime pp and a positive integer nn, let νp(n)\nu_{p}(n) be the largest nonnegative integer kk for which pkp^{k} divides nn. Taking νp\nu_{p} on both sides of the given equation, we get νp(a)+νp(b)=2νp(a)νp(b)\nu_{p}(a)+\nu_{p}(b)=2 \cdot\left|\nu_{p}(a)-\nu_{p}(b)\right| which means νp(a)νp(b){3,13}\frac{\nu_{p}(a)}{\nu_{p}(b)} \in\left\{3, \frac{1}{3}\right\} for all primes pp. Using this with a,b100a, b \leq 100, we get that - We must have (ν2(a),ν2(b)){(0,0),(1,3),(3,1),(2,6),(6,2)}\left(\nu_{2}(a), \nu_{2}(b)\right) \in\{(0,0),(1,3),(3,1),(2,6),(6,2)\} because aa and bb cannot be divisible by 272^{7}. - We must have (ν3(a),ν3(b)){(0,0),(1,3),(3,1)}\left(\nu_{3}(a), \nu_{3}(b)\right) \in\{(0,0),(1,3),(3,1)\} because aa and bb cannot be divisible by 36>1003^{6}>100. - aa and bb cannot be divisible by any prime p5p \geq 5, because if not, then one of aa and bb must be divisible by p353>100p^{3} \geq 5^{3}>100. If (ν2(a),ν2(b))=(2,6)\left(\nu_{2}(a), \nu_{2}(b)\right)=(2,6) (and similarly with (6,2)(6,2) ), then we must have (a,b)=(4,64)(a, b)=(4,64), so the sum is 68 . If (ν3(a),ν3(b))=(1,3)\left(\nu_{3}(a), \nu_{3}(b)\right)=(1,3) (and similarly with (3,1)(3,1) ), then we must have ν2(b)1\nu_{2}(b) \leq 1 (otherwise, bb \geq 2233>100)\left.2^{2} \cdot 3^{3}>100\right). Hence, the optimal pair is (a,b)=(2331,2133)=(24,54)(a, b)=\left(2^{3} \cdot 3^{1}, 2^{1} \cdot 3^{3}\right)=(24,54), so the sum is 24+54=7824+54=78. If neither of the above happens, then a+b21+2310a+b \leq 2^{1}+2^{3} \leq 10, which is clearly not optimal. Hence, the optimal pair is (24,54)(24,54), and the answer is 78 .

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.