Formula To Find Ordered & Unordered Pairs Possible For A Given LCM - Hemant Malhotra


  • Director at ElitesGrid | CAT 2016 - QA : 99.94, LR-DI - 99.70% / XAT 2017 - QA : 99.975


    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^2

    So, 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 y

    so 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 = 48

    so unordered = x + y + z = 48 + 24 + 1 = 73



  • in the last question about unordered pairs, in case b when two are same and one is different. You have first got the number of ordered pairs for 2 numbers (let it be a), and then multiplied it by 3 to get the arrangements. My confusion is, shouldn't we divide a by 2 and then multiply the number by 3 ? Because since a is number of ordered pairs, we have to make it unordered first and then multiply the arrangements to make it ordered. So instead of 24, it should be 24/2 = 12. Please clarify


Log in to reply
 

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.