Suppose there are two numbers - a and b. If a number a divides another number b exactly, we say that a is factor of b and b is called multiple of a.
Highest Common Factor (HCF) or Greatest Common Divisor (GCD)
The greatest common divisor (gcd), also known as the greatest common denominator, greatest common factor (gcf), or highest common factor (hcf), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.
The HCF of two or more than two numbers is the greatest number that divides each of them exactly. There are two methods of finding the HCF of a given set of numbers:
1. Factorisation Method
In this method, express each one of the given numbers as the product of prime factors. The product of least powers of common prime factors gives HCF.
2. Division Method
Divide the larger number by the smaller one. Now, divide the divisor by the remainder. Repeat the process of dividing the preceding number by the remainder last obtained till zero is obtained as remainder. The last divisor is the required HCF.
Finding the HCF of more than two numbers: H.C.F. of [(H.C.F. of any two) and (the third number)] gives the HCF of three given numbers.
Least Common Multiple (LCM)
The lowest common multiple or (LCM) least common multiple or smallest common multiple of two rational numbers a and b is the smallest positive rational number that is an integer multiple of both a and b. The definition can be generalised for more than two numbers.
The least number which is exactly divisible by each one of the given numbers is called their LCM.
1. Factorisation Method of Finding LCM
Resolve each one of the given numbers into a product of prime factors. Then, LCM is the product of highest powers of all the factors.
2. Common Division Method (Short-cut Method) of Finding LCM
Arrange the given numbers in a row in any order. Divide by a number which divides exactly at least two of the given numbers and carry forward the numbers which are not divisible. Repeat the above process till no two of the numbers are divisible by the same number except 1. The product of the divisors and the undivided numbers is the required LCM of the given numbers.
Product of two numbers = Product of their HCF and LCM
a x b = HCF x LCM
Two numbers are said to be co-primes if their HCF is 1. HCF of two co-prime numbers is 1. To find LCM of co-prime numbers, just multiply them. No need to find factors.
HCF and LCM of Fractions
HCF = (HCF of Numerators) / (LCM of Denominator)
LCM = (LCM of Numerators) / (HCF of Denominator)
Applications of HCF and LCM
1. Find the Greatest Number that will exactly divide x, y, z.
Required number = H.C.F. of x, y, and z (greatest divisor).
2. Find the Greatest Number that will divide x, y and z leaving remainders a, b and c respectively.
Required number (greatest divisor) = H.C.F. of (x – a), (y – b) and (z – c).
3. Find the Least Number which is exactly divisible by x, y and z.
Required number = L.C.M. of x, y and z (least divided).
4. Find the Least Number which when divided by x, y and z leaves the remainders a, b and c respectively.
Then, it is always observed that (x – a) = (z – b) = (z – c) = K (say).
∴ Required number = (L.C.M. of x, y and z) – K.
5. Find the Least Number which when divided by x, y and z leaves the same remainder ‘r’ each case.
Required number = (L.C.M. of x, y and z) + r.
6. Find the Greatest Number that will divide x, y and z leaving the same remainder in each case.
Required number = H.C.F of (x – y), (y – z) and (z – x).
Example 1: What is the greatest number which exactly divides 110, 154 and 242?
The required number is the HCF of 110, 154 and 242.
110 = 2 × 5 × 11
154 = 2 × 7 × 11
242 = 2 × 11 × 11
∴ HCF = 2 × 11 = 22
Example 2: What is the greatest number, which when divides 3 consecutive odd numbers produces a remainder of 1.
If x, y, z be 3 consecutive odd numbers, then the required number will be the HCF of x – 1, y – 1 and z – 1.
Since x-1, y-1 and z-1 are 3 consecutive even integers, their HCF will be 2.
So, the answer is 2.
Example 3: What is the highest 3 digit number, which is exactly divisible by 3, 5, 6 and 7?
The least number which is exactly divisible by 3, 5, 6, and 7 is LCM(3, 5, 6, 7) = 210.
So, all the multiples of 210 will be exactly divisible by 3, 5, 6 and 7.
So, such greatest 3 digit number is 840 (210 × 4).
Example 4: In a farewell party, some students are giving pose for photograph, If the students stand at 4 students per row, 2 students will be left if they stand 5 per row, 3 will be left and if they stand 6 per row 4 will be left. If the total number of students are greater than 100 and less than 150, how many students are there?
If ‘N’ is the number of students, it is clear from the question that if N is divided by 4, 5, and 6, it produces a remainders of 2, 3, & 4 respectively.
Since (4 – 2) = (5 – 3) = (6 – 4) = 2, the least possible value of N is LCM(4, 5, 6) – 2 = 60 – 2 = 58.
But, 100 < N < 150.
So, the next possible value is 58 + 60 = 118
Example 5: There are some students in the class. Mr.X brought 130 chocolates and distributed to the students equally, then he was left with some chocolates. Mr Y brought 170 chocolates and distributed equally to the students. He was also left with the same no of chocolates as Mr X was left. Mr Z brought 250 chocolates, did the same thing and left with the same no of chocolates. What is the max possible no of students that were in the class?
The question can be stated as, what is the highest number, which divides 130, 170 and 250 gives the same remainder, i.e. HCF of (170 −130), (250 −170), (250 −130).
I.e. HCF (40, 80, 120) = 40.