Problem:
Suppose and be positive integers not exceeding such that
Compute the largest possible value of .
HMMT November, 2023
Solution
Solution:
For any prime and a positive integer , let be the largest nonnegative integer for which divides . Taking on both sides of the given equation, we get
which means for all primes . Using this with , we get that
- We must have because and cannot be divisible by .
- We must have because and cannot be divisible by .
- and cannot be divisible by any prime , because if not, then one of and must be divisible by .
If (and similarly with ), then we must have , so the sum is .
If (and similarly with ), then we must have (otherwise, ). Hence, the optimal pair is , so the sum is .
If neither of the above happens, then , which is clearly not optimal.
Hence, the optimal pair is , and the answer is .
Want a route through all this instead of an archive? The track
puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.