HCF & LCM Concepts - Anubhav Sehgal, NMIMS Mumbai

[anubhav_sehgal]

Keynote 1
If a = bq + r, then HCF(a,b) = HCF(b,r) ; a>b>0 [ EUCLIDEAN Algorithm ]

Keynote 2
HCF(a, b) = HCF(a + b, b) = HCF(a - b, b) ; a>b

Keynote 3
HCF(na, nb) = n * HCF(a,b) and LCM(na, nb) = n * LCM(a,b)

Keynote 4
LCM of first X natural numbers/LCM of first Y natural numbers = Product of primes between X and Y multiplied by additional powers of primes existing in LCM of first Y natural numbers ; X > Y
example LCM of (1,2,3,4,5,6,7,8) / LCM of (1,2,3,4,5) = 7 * 2 = 14
The 2 multiplied is for extra two from 8 that appears in numerator while 2^2 = 4 is already accounted for in denominator.

LCM(1,2,…,16)/LCM(1,2,3,4,5) = 7 * 11 * 13 * (2^2) * 3
2^2 is for two extra from 16 = 2^4 which were not present in highest power of 2 in LCM of 1 to 5
[4 = 2^2 was the highest power ]

Keynote 5
LCM (a, b) * HCF (a, b) = Product of a and b
If HCF of a set of numbers is 1 then their product is equal to their LCM.

Keynote 6
LCM of fractions = LCM of numerators/HCF of denominators AND
HCF of fractions = HCF of numerators/LCM of denominators

Keynote 7
HCF (a + b, LCM (a, b)) = HCF (a, b)

Keynote 8
LCM >= Numbers >= HCF always
HCF is a factor of LCM always
If HCF = LCM => all numbers are equal.

Keynote 9
n! is always divisible by LCM of first n natural numbers.
Furthermore,
LCM of first n natural numbers = n! for n = 1, 2, 3
LCM of first n natural numbers = n!/2 for n = 4,5
and can be extended similarly.

Keynote 10
(n + 1) * LCM (C (n, 0), C (n, 1), …, C (n, n)) = LCM (1, 2, 3, … , n + 1)

Keynote 11
LCM of two numbers = a^p * b^q * c^r * …
Number of unordered sets = [(2p + 1)(2q + 1)(2r + 1). . – 1]/2 = S3
Number of ordered sets = (2p + 1)(2q + 1)(2r + 1). . + 1(optional)

Explanation
Let LCM = 30 = 2^1 * 3^1 * 5^1 i.e p = q = r = 1
Let a = 2^x1 * 3^y1 * 5^z1 and b = 2^x2 * 3^y2 * 5^z2
If x1 = 1, then x2 has two options 0,1 i.e (p + 1) options
If x2 = 1, then x1 has two options 0,1 i.e (p + 1) options
So a total of 2 * 2 = 4 options. But if you note here we counted x1,x2 = 1,1 twice.
Hence we have 2 * 2 – 1 = 3 options for power of 2.
So, in general, 2(p + 1) – 1 = 2p + 1 options.
Similarly for other powers. Hence, ordered sets = (2p + 1)(2q + 1)(2r + 1)…
Here we will thus have : 3 * 3 * 3 = 27 ordered sets.

Now sets for two numbers can be a, b or b, a or a, a form.
For unordered sets we remove the a, a form sets and split the rest in half to get unordered sets.
Unordered sets = [(2p + 1)(2q + 1)(2r + 1). . – 1]/2 + 1(optional, added back if we can have the two numbers to be same)

Keynote 12
LCM of three numbers = a^p * b^q * c^r * . .
Ordered Sets (S1) = [(p + 1)^3 – p^3][(q + 1)^3 – q^3][(r + 1)^3 – r^3]
Unordered sets = [ S1 – 3 * 2 * S3 – 1]/6 + (Optional : 2S3 + 1 added back if numbers must not be distinct)

Explanation
example : LCM = 150 = 2 * 3 * 5^2 = N
Let the three numbers be a, b and c.
If a = 2^x1 * 3^y1 * 5^z1 , b = 2^x2 * 3^y2 * 5^z2 and c = 2^x3 * 3^y3 * 5^z3
Now for LCM of a, b, c to be 2 * 3 * 5^2
Let’s consider for the prime 2 first. So, p = 1 here.
x1, x2 and x3 may take any values from 0,1. But all cannot be zero else LCM will have power of 2 as zero. Hence (p + 1) options for each of the three numbers for any prime with power p in LCM. Out of which we need to remove the cases when all numbers have powers of a particular prime less than that required in LCM. So in that case each number will take any of the p values from 0 to (p – 1) i.e p options.

Let’s take another prime, this time 5. r = 2 here.
So z1, z2 and z3 may take any of the values from 0, 1, 2 i.e (r + 1) options for each of the three numbers.
So, (r + 1) * (r + 1) * (r + 1) = (r + 1)^3 ways. But if all the three numbers take power of 5 from 0,1 and none of them has power as 2 then LCM won’t have r = 2. So we remove cases where each of the three numbers take power of 5 from 0,1 only i.e r options for each number and a total of r^3 ways.

Hence, this way we get : Ordered sets(S1) = [(p + 1)^3 – p^3] [(q + 1)^3 – q^3][(r + 1)^3 – r^3]

Now for three numbers we have following type of sets existing:

1. All distinct : x, y, z form. Having 3! Arrangements considered in ordered sets. For unordered sets we need to count 1 case only for each of the 3! Arrangements of the same set.
2. Two same : x, x, y form or y, y, x form. These involve selection of 2 variables one for being same and one for being the different one and are arranged in 3!/2! Ways in ordered sets. Hence they are present in 3!/2! * 2c1 ways in our ordered sets. This is essentially same as number of ways of having LCM of two numbers x, y chosen as the given LCM.
3. All same : x, x, x. This is the case when the three numbers are equal to LCM itself.

So for unordered sets, [S1 – 3!/2! * 2 * (Unordered sets for LCM(x,y) = N) – 1]/3! + 2 * (Unordered sets for LCM(x,y) = N) + 1 {Optional addition in case of non-distinct nos}

We basically remove the cases where ordering is not of distinct numbers, divide it by permutation for distinct numbers to count all ordered sets of same numbers as just one and then add back the cases where numbers were not distinct optionally if required.

For N = 150,
Ordered = 7 * 7 * 19 = 931
Unordered = (931 – 3!/2! * 2 * {[(2(1) + 1)(2(1) + 1)(2(2) + 1) – 1]/2} – 1)/3! + 2 * S3 + 1
Unordered = (931 – 3 * 2 * 22 – 1)/6 + 2 * 22 + 1 = 178

Take some time to sink it in. Read step by step. Write the sets manually by taking a small number and then read the explanation in context with that. Clear your ordering and unordering on a generic level through this discussion.

Keynote 13
Number of co-prime factor pairs of N = a^p * b^q * c^r * …
Ordered sets = (2p + 1)(2q + 1)(2r + 1). .
Unordered sets = [(2p + 1)(2q + 1)(2r + 1) – 1]/2 + 1(optional)

Explanation
example : N = 10 = 2^1 * 5^1 ; Factors are 1,2,5,10
Co-prime pairs as seen manually will be: (1, 1) ; (1, 2) ; (1, 5) ; (1, 10) ; (2, 5)
Pairs are of the form : (1, 1) ; (1, 2^p) ; (1, 5^q) ; (1, 2^p * 5^q) ; (2^p, 5^q)
In general, ordered pairs will be,
1 : for (1 ,1)
2 * p: for (1, a^p) like (1, 2) ; (1, 4) ; (2, 1) ; (4, 1) if the power of 2 in N is 2.
2 * q: for (1, b^q)
and so on for individual power of primes. Then,
2 * pq: for (1, a^p * b^q) form
2 * pq: for (a^p, b^q) form
So adding them all up : 1 + 2p + 2q + 4pq = (2p + 1)(2q + 1)
and in general, Ordered sets = (2p + 1)(2q + 1)(2r + 1)..

For Unordered, you remove the 1,1 case and divide it by 2! To count distinct number sets as one for all permutations of it and add back as per requirement of question (optional).
Unordered sets = [(2p + 1)(2q + 1)(2r + 1).. – 1]/2 + 1(optional)

Keynote 14
Number of co-prime factor triplets of N = a^p * b^q * c^r * . . .
Ordered(S1) = (3p + 1)(3q + 1)(3r + 1)
Unordered = [S1 – 3*(f – 1) – 1]/6 + {Optional added back if required : (f – 1) + 1 }
where f : No of factors of N

Explanation
example : 10 = 2 * 5
Co-prime triplets by manual count : (1, 1, 1) ; (1, 1, 2) ; (1, 1, 5) ; (1, 1, 10) ; (1, 2, 5)
So basically we have three types of sets here :
All distinct : (1, a^p, b^q) form ; Here (1, 2, 5) only as power of 2 and 5 is one.
So, number of ordered arrangements = 3! * p * q
Two same : (1, 1, a^p) ; (1, 1, b^q) ; (1, 1, a^p*b^q).
Number of ordered arrangements = 3!/2! * (p + q + pq)
All same : (1, 1, 1) ; Always only one.
Ordered sets (S1) = 3! * pq + 3!/2!(p + q + pq) + 1 = 9pq + 3p + 3q + 1 = (3p + 1)(3q + 1) which can be extended to the stated keynote for a generic prime factorization.
Unordered sets = [S1 – 3!/2! * (No of factors – 1) – 1]/6 + (f – 1) + 1 {optionally added back}