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

Home > Just Math
LCM by pairs (Posted on 2013-10-14) Difficulty: 2 of 5
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.)
Solution 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
Please log in:
Remember me:
Sign up! | Forgot password

Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Copyright © 2002 - 2019 by Animus Pactum Consulting. All rights reserved. Privacy Information