Determine the total number of pairs (x, y) of positive integers such that the least common multiple (LCM) of x and y is 23*57*1113.
For each of the prime factors, either x must be divisible by highest power, or y is. For example, either x is divisible by 2^3, or y is. If x is divisible by 2^3, then y has n factors of 2, where n <= 3.
So if we were only talking about lcm(x,y)=2^3, there would be 4 solutions: (8,1), (8,2), (8,4), (8,8)
Note that 3 of these pairs are asymmetric, and one is symmetric (x=y). If the order of x and y matters, then there would really be 7 solutions. Similarly, there are 15 solutions to lcm(x,y)=5^7, and 27 solutions to lcm(x,y)=11^13.
Going back to the original problem, the answer should be 7*15*27, if the order of x and y matters. That's 2835.
If the order does not matter, then we are double-counting most solutions. The only solution we are not double-counting is the one where x=y=23*57*1113. So the number of solutions is (2835+1)/2=1418.
Thanks to Ady for pointing out the importance of whether we're considering ordered or unordered pairs.
|
|
Posted by Tristan
on 2013-10-14 13:07:13 |
Analytical Solution
