What is highest common factor (HCF) and least common multiple (LCM)? How do you calculate HCF and LCM of two or more numbers? Are you looking for problems on HCF and LCM? This chapter will answer all these questions.

**HIGHEST COMMON FACTOR (HCF)**

The largest number that divides two or more given numbers is called the highest common factor (HCF) of those numbers. There are two methods to find HCF of the given numbers:

__Prime Factorization Method__- When a number is written as the product of prime numbers, the factorization is called the prime factorization of that number. For example, 72 = 2 × 2 × 2 × 3 × 3 = 2^{3} × 3^{2}

To find the HCF of given numbers by this method, we perform the prime factorization of all the numbers and then check for the **common** prime factors. For every prime factor common to all the numbers, we choose the least index of that prime factor among the given number. The HCF is product of all such prime factors with their respective least indices.

**EXAMPLE**

Find the HCF of 72, 288, and 1080

Answer:

72 = 2^{3} × 3^{2},

288 = 2^{5} × 3^{2},

1080 = 2^{3} × 3^{3} × 5

The prime factors common to all the numbers are 2 and 3. The lowest indices of 2 and 3 in the given numbers are 3 and 2 respectively.

Hence, HCF = 2^{3} × 3^{2} = 72.

Find the HCF of 36x^{3}y^{2} and 24x^{4}y.**Answer:**

36x^{3}y^{2} = 2^{2}∙3^{2}∙x^{3}∙y^{2}

24x^{4}y = 2^{3}∙3∙x^{4}∙y.

The least index of 2, 3, x and y in the numbers are 2, 1, 3 and 1 respectively.

Hence the HCF = 2^{2}∙3∙x^{2}∙y = 12x^{2}y.

__Division method__- To find HCF of two numbers by division method, we divide the higher number by the lower number. Then we divide the lower number by the first remainder, the first remainder by the second remainder... and so on, till the remainder is 0. The last divisor is the required HCF.

**EXAMPLE**

Find the HCF of 288 and 1080 by the division method.

Answer:

Hence, the last divisor 72 is the HCF of 288 and 1080.

**CONCEPT OF CO-PRIME NUMBERS: **Two numbers are co-prime to each other if they have no common factor except 1. For example, 15 and 32, 16 and 5, 8 and 27 are the pairs of co-prime numbers. If the HCF of two numbers N_{1} and N_{2} be H, then, the numbers left after dividing N_{1} and N_{2} by H are **co-prime** to each other.

Therefore, if the HCF of two numbers be A, the numbers can be written as Ax and Ay, where x and y will be co-prime to each other.

**SOLVED PROBLEMS ON HCF**

Three company of soldiers containing 120, 192, and 144 soldiers are to be broken down into smaller groups such that each group contains soldiers from one company only and all the groups have equal number of soldiers. What is the least number of total groups formed?

Answer: The least number of groups will be formed when each group has number of soldiers equal to the HCF. The HCF of 120, 192 and 144 is 24. Therefore, the numbers of groups formed for the three companies will be 5, 8, and 6, respectively. Therefore, the least number of total groups formed = 5 + 8 + 6 = 19.

The numbers 2604, 1020 and 4812 when divided by a number N give the same remainder of 12. Find the highest such number N.

Answer: Since all the numbers give a remainder of 12 when divided by N, hence (2604 – 12), (1020 – 12) and (4812 – 12) are all divisible by N. Hence, N is the HCF of 2592, 1008 and 4800. Now 2592 = 2^{5} × 3^{4}, 1008 = 2^{4} × 3^{2} × 7 and 4800 = 2^{6} × 3 × 5^{2}. Hence, the number N = HCF = 2^{4} × 3 = 48.

The numbers 400, 536 and 645, when divided by a number N, give the remainders of 22, 23 and 24 respectively. Find the greatest such number N.

Answer: N will be the HCF of (400 – 22), (536 – 23) and (645 – 24). Hence, N will be the HCF of 378, 513 and 621. à N = 27.

The HCF of two numbers is 12 and their sum is 288. How many pairs of such numbers are possible?

Answer: If the HCF if 12, the numbers can be written as 12x and 12y, where x and y are co-prime to each other. Therefore, 12x + 12y = 288 --> x + y = 24.

The pair of numbers that are co-prime to each other and sum up to 24 are (1, 23), (5, 19), (7, 17) and (11, 13). Hence, only four pairs of such numbers are possible. The numbers are (12, 276), (60, 228), (84, 204) and (132, 156).

The HCF of two numbers is 12 and their product is 31104. How many such numbers are possible?

Answer: Let the numbers be 12x and 12y, where x and y are co-prime to each other. Therefore, 12x × 12y = 31104 --> xy = 216. Now we need to find co-prime pairs whose product is 216.

216 = 2^{3} × 3^{3}. Therefore, the co-prime pairs will be (1, 216) and (8, 27). Therefore, only two such numbers are possible.

**LEAST COMMON MULTIPLE (LCM)**

The least common multiple (LCM) of two or more numbers is the lowest number which is divisible by all the given numbers.

To calculate the LCM of two or more numbers, we use the following two methods:

__Prime Factorization Method__: After performing the prime factorization of the numbers, i.e. breaking the numbers into product of prime numbers, we find the highest index, among the given numbers, of all the prime numbers. The LCM is the product of all these prime numbers with their respective highest indices.

**EXAMPLE**

Find the LCM of 72, 288 and 1080.

Answer: 72 = 2^{3} × 3^{2}, 288 = 2^{5} × 3^{2}, 1080 = 2^{3} × 3^{3} × 5

The prime numbers present are 2, 3 and 5. The highest indices (powers) of 2, 3 and 5 are 5, 3 and 1, respectively.

Hence the LCM = 2^{5} × 3^{3} × 5 = 4320.

Find the LCM of 36x^{3}y^{2} and 24x^{4}y.

**Answer: 36x**^{3}y^{2} = 2^{2}∙3^{2}∙x^{3}∙y^{2} 24x^{4}y = 2^{3}∙3∙x^{4}∙y.

The highest indices of 2, 3, x and y are 3, 2, 4 and 2 respectively.

Hence, the LCM = 2^{3}∙3^{2}∙x^{4}∙y^{2} = 72x^{4}y^{2}.

__Division Method__: To find the LCM of 72, 196 and 240, we use the division method in the following way:

L.C.M. of the given numbers = product of divisors and the remaining numbers

= 2 × 2 × 2 × 3 × 3 × 10 × 49 = 72 × 10 × 49 = 35280.

**PROPERTIES OF HCF AND LCM**

· The HCF of two or more numbers is smaller than or equal to the smallest of those numbers.

· The LCM of two or more numbers is greater than or equal to the largest of those numbers

· If numbers N_{1}, N_{2}, N_{3}, N_{4} etc. give remainders R_{1}, R_{2}, R_{3}, R_{4}, respectively, when divided by the same number P, then P is the HCF of (N_{1} – R_{1}), (N_{2} – R_{2}), (N_{3} – R_{3}), (N_{4} – R_{4}) etc.

· If the HCF of numbers N_{1}, N_{2}, N_{3} … is H, then N_{1}, N_{2}, N_{3}... can be written as multiples of H (Hx, Hy, Hz.. ). Since the HCF divides all the numbers, every number will be a multiple of the HCF.

· If the HCF of two numbers N_{1} and N_{2} is H, then, the numbers (N_{1} + N_{2}) and (N_{1} – N_{2}) are also divisible by H. Let N_{1} = Hx and N_{2} = Hy, since the numbers will be multiples of H. Then, N_{1} + N_{2} = Hx + Hy = H(x + y), and N_{1} – N_{2} = Hx – Hy = H(x – y). Hence both the sum and differences of the two numbers are divisible by the HCF.

· If numbers N_{1}, N_{2}, N_{3}, N_{4} etc. give an equal remainder when divided by the same number P, then P is a factor of (N_{1} – N_{2}), (N_{2} – N_{3}), (N_{3} – N_{4})…

· If L is the LCM of N_{1}, N_{2}, N_{3}, N_{4}.. all the multiples of L are divisible by these numbers.

· If a number P always leaves a remainder R when divided by the numbers N_{1}, N_{2}, N_{3}, N_{4} etc., then P = LCM (or a multiple of LCM) of N_{1}, N_{2}, N_{3}, N_{4}.. + R.

**SOLVED PROBLEMS ON LCM**

Find the highest four-digit number that is divisible by each of the numbers 24, 36, 45 and 60.

Answer: 24 = 2^{3} × 3, 36 = 2^{2} × 3^{2}, 45 = 3^{2} × 5 and 60 = 2^{3} × 3^{2} × 5.

Hence, the LCM of 24, 36, 45 and 60 = 2^{3} × 3^{2} × 5 = 360.

The highest four-digit number is 9999. 9999 when divided by 360 gives the remainder 279. Hence, the number (9999 – 279 = 3720) will be divisible by 360.

Hence the highest four-digit number divisible by 24, 36, 45 and 60 = 3720.

Find the highest number less than 1800 that is divisible by each of the numbers 2, 3, 4, 5, 6 and 7.

Answer: The LCM of 2, 3, 4, 5, 6 and 7 is 420. Hence 420, and every multiple of 420, is divisible by each of these numbers. Hence, the number 420, 840, 1260, and 1680 are all divisible by each of these numbers. We can see that 1680 is the highest number less than 1800 which is multiple of 420.

Hence, the highest number divisible by each one of 2, 3, 4, 5, 6 and 7, and less than 1800 is 1680.

Find the lowest number which gives a remainder of 5 when divided by any of the numbers 6, 7, and 8.

Answer: The LCM of 6, 7 and 8 is 168. Hence, 168 is divisible by 6, 7 and 8. Therefore, 168 + 5 = 173 will give a remainder of 5 when divided by these numbers.

What is the smallest number which when divided by 9, 18, 24 leaves a remainder of 5, 14 and 20 respectively?

Answer: The common difference between the divisor and the remainder is 4 (9 - 5 = 4, 18 - 14 = 4, 24 - 20 = 4). Now the LCM of 9, 18, and 24 is 72.

Now 72 - 4 = 72 - 9 + 5 = 72 - 18 + 14 = 72 - 24 + 20. Therefore, if we subtract 4 from 72, the resulting number will give remainders of 5, 14, and 20 with 9, 18, and 24.

Hence, the number = 72 - 4 = 68.

A number when divided by 3, 4, 5, and 6 always leaves a remainder of 2, but leaves no remainder when divided by 7. What is the lowest such number possible?

Answer: the LCM of 3, 4, 5 and 6 is 60. Therefore, the number is of the form 60k + 2, i.e. 62, 122, 182, 242 etc. We can see that 182 is divisible by 7. Therefore, the lowest such number possible = 182.

Thanks for Sharing Quality information With us

ReplyDeleteGMAT coaching|Best GMAT Coaching Centre|Sandeep Gupta|Top One Percent Gmat