All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 LCM by pairs (Posted on 2013-10-14)
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.

 No Solution Yet Submitted by K Sengupta No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Analytical Solution | Comment 3 of 4 |
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

 Search: Search body:
Forums (0)