Browse · MATH
Printjmc
number theory senior
Problem
When the least common multiple of two positive integers is divided by their greatest common divisor, the result is 33. If one integer is 45, what is the smallest possible value of the other integer?
Solution
Let be the other integer, so We know that for all positive integers and , so Dividing this equation by the previous equation, we get so .
Since 11 divides the left-hand side, 11 also divides the right-hand side, which means is divisible by 11. Also, 15 divides the right-hand side, so 15 divides the left-hand side, which means is divisible by 15. Since , is divisible by 15. Hence, must be divisible by .
Note that and , and , so is achievable and the smallest possible value of is .
Since 11 divides the left-hand side, 11 also divides the right-hand side, which means is divisible by 11. Also, 15 divides the right-hand side, so 15 divides the left-hand side, which means is divisible by 15. Since , is divisible by 15. Hence, must be divisible by .
Note that and , and , so is achievable and the smallest possible value of is .
Final answer
165