Formula To Find Ordered & Unordered Pairs Possible For A Given LCM - Hemant Malhotra
-
First let us understand some basic things about LCM
We know LCM of 2^3 * 3^2 and 2^2 * 3^3 is 2^3 * 3^3
Here we look for highest power of 2 and highest power 3. Now if we want to find LCM of 2^3 * 3^3 and 2^3 * 3^3 LCM will be still 2^3 * 3^3. so if highest power is same in both the number there will be no effect in LCM
so highest power should be distributed in atleast one of the number.
If LCM of a and b is 2^3 * 3^3 then we will say that 2^3 will be in a or will be in b or will be in a and b both , same for 3^3. Got the concept ? We will solve a question.
The LCM of three positive integers a, b, c is 119^2. Find the total number of ordered triplets (a, b, c)
119^2 = 17^2 * 7^2.
LCM is 17^2 * 7^2So, powers of 17 till the maximum power available (17^0, 17^1, 17^2) and powers of 7 till the maximum power available 7 (7^0, 7^1, 7^2) will be distributed among a, b, c such that at least one of a, b, c has the highest power of 17 and at least one of them has the highest power of 7.
Each of a, b, c can have any one of three powers of 17 in 3 ways. => a, b and c can have powers of 17 in 3 * 3 * 3 = 27 ways. But this will also contain cases when a, b, c will not have highest power of 17 so we have to remove those cases.
Cases where highest power is in none of a, b and c is in 2 ways for each of a, b and c = > a, b and c cannot have highest power of 17 in 2 * 2 * 2 = 8 ways.
at least one = total cases - cases when none of them has highest power
a, b and c can have powers of 17, such that at least one of them has the highest power of 17, in 27 - 8 = 19 ways.
Similarly, a, b and c can have powers of 7, such that at least one of them has the highest power of 7, in 19 ways.
so total ways = 19 * 19 = 361
Case 1- Number of ordered pairs when LCM is given
let two numbers x and y and their LCM is 2^2 * 3^3 * 5^3
now atleast one of x and y , highest power of 2 is 2. highest power of 3 is 3 and highest power of 5 is 3
now let's take 2^2 so x can be 2^0 or 2^1 or 2^2. same in case of yso 3 * 3 = 3^2 ways for them
but there will be a case when neither x nor y have the power 2^2 so we have to remove that case because LCM won't be 2^2
so we will remove cases when x and y have only 2^0 or 2^1
so 2 * 2 = 2^2 cases to be removed
so total cases = 3^2 - 2^2 = 5 = 2 * 2 + 1
Similarly when we choose 3^3 then total cases = 4^2 - 3^2 = 7 = 2 * 3 + 1
For case of 5^3, it is 4^2 - 3^2 = 7 = 2 * 3 + 1
so Total case = (3^2 - 2^2) * ( 4^2 - 3^2) * ( 4^2 - 3^2)
= (2 * 2 + 1) (2 * 3 + 1) (2 * 3 + 1)
See the pattern ?
So the formula is
Number of ordered pairs possible for LCM = N = P1^a x P2^b x P3^c
= [(a + 1)^2 - a^2] [b+1)^2 - b^2] [(c + 1)^2 - c^2]
= (2a + 1) (2b + 1) (2c + 1)
Where, a, b and c are power of prime factors
Example : If LCM of two numbers is 360, how many such ordered pairs are possible?
360 = 2^3 * 3^2 * 5
so our formula is (2a + 1)(2b + 1)(2c + 1, where a , b and c are power of prime
So [(2 * 3 + 1)(2 * 2 + 1)(2 * 1 + 1) = 7 * 5 * 3 = 105
Case 2 - Number of unordered pairs when LCM is given
The LCM of three positive integers x, y and z is 119^2. Find the total number of unordered triplets (x, y and z)
We solved previously for total ordered as 361. Now how to Find Unordered
Ordered = With arrangement and Unordered = (Without arrangement)
Case1 - when all are different
Case 2 - when 2 are same and one is different
Case 3 - when all are same
a) case1- when all are different : let those cases are x and number of ways to arrange them = 3! = 6 so 6x
b) cases when two are same and one is different : means basically we want to find ordered pair of 2 numbers
those will be (2a + 1) (2b + 1) = (2 * 2 + 1) (2 * 2 + 1) = 25 but this will also contain case when all three are equal so we need to remove that.
so 24 cases. Now ways to arrange them 3!/2! = 3
so total 24 * 3 = 72
Case3 - when all are same. Only 1 case will be there
so ordered = 361
361= 6x + 72 + 1
x = (361 - 73)/6
x = 48so unordered = x + y + z = 48 + 24 + 1 = 73
