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

1

1

1

1

1

1

1

1