Maths Olympiad Prep

Library / /632 of 740

, 2023

Number theory Difficulty 5.4 AIME, harder Prove it United States

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

Solution

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 \{3, \frac{1}{3}\} 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 6868.

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, b2233>100b \geq 2^{2} \cdot 3^{3} > 100). Hence, the optimal pair is (a,b)=(2331,2133)=(24,54)(a, b) = (2^{3} \cdot 3^{1}, 2^{1} \cdot 3^{3}) = (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 7878.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.