Browse · MATH
Printjmc
number theory senior
Problem
The greatest common divisor of two positive integers less than is equal to . Their least common multiple is twelve times one of the integers. What is the largest possible sum of the two integers?
Solution
Let the two integers be and . Then, and, without loss of generality, let . Multiplying the two equations yields that . Using the identity that , it follows that , and so .
Since , we know is divisible by 3. However, cannot be divisible by , because if was divisible by 9, then would be divisible by 9 as well, since 36 is divisible by 9. This cannot occur since . Similarly, cannot be divisible by 2, because if were divisible by 2, then would be divisible by 2 as well, since 36 is divisible by 2.
In summary, is a multiple of 3, but not 9, and is not divisible by 2. The largest such number less than 100 is 93. We can verify that , so the largest possible sum of is .
Since , we know is divisible by 3. However, cannot be divisible by , because if was divisible by 9, then would be divisible by 9 as well, since 36 is divisible by 9. This cannot occur since . Similarly, cannot be divisible by 2, because if were divisible by 2, then would be divisible by 2 as well, since 36 is divisible by 2.
In summary, is a multiple of 3, but not 9, and is not divisible by 2. The largest such number less than 100 is 93. We can verify that , so the largest possible sum of is .
Final answer
129