HCF & LCM - Basics 1

Sunday, May 21, 2006

Now that we are familiar with basics let us move on, not that we won't look into basics again, for time being. Since our study is progressing and in a progressive manner, next thing to know would be HCF and LCM, at this point of time.

Factors: We have covered factors in previous posts. Let us refresh. Suppose x and y are two integers, if x divides y completely, means the remainder is zero, then we can say that x is a factor of y. Example, 6 and 3, where 3 divides 6 completely, hence 3 is a factor of 6. What are the other factors of 6? Find out, 1, 2, 3 and 6 correct.

Common Factors: What is common factor of 6? None, because to find out common factor we need two numbers. Lets take 2 and 6, what are the common factors of 2 and 6? 2 = 1, 2, 6 = 1, 2, 3 and 6, so 1 and 2 are common factors, correct. Now lets take 12 and 30, what are the common factors of 12 and 30? 1, 2, 3 and 6 correct. So are we done? Not yet.

Highest Common Factors (HCF): Look at the above example, what is the highest common factor between 12 and 30? 6, Yeah. Basically HCF is the largest common factor between any numbers. HCF is also known as GCD (Greatest Common Divisor)

Before knowing how to find highest common factor, I would like to introduce the concept of Prime Factors.

Prime Factors: Now we all know that all the numbers are composed of factors, but if you look closely, as a matter of fact, all the numbers are composed of primes. Lets take 36, i.e 36 = 4 x 9 i.e 2^2 x 3^3, because 4 = 2 x 2 and 9 = 3 x 3. Conclusion? All the number are composed of primes. Of course Primes themselves don't have factors.

Q) Why should I learn about HCF?
A) Suppose you have 20 Banana trees, 12 Apple trees and 24 Mango trees, you want to plant them in such a way that there should be equal amount of trees in each row of each type of tree. How many rows will each type of tree take? Logically you want to find out the common number of trees in these three set of trees which will peacefully solve our problem. HCF comes handy in such kind of problems, where you want to find the highest such common number.

20 = 2^2 x 5
12 = 2^2 x 3
24 = 2^3 x 3

HCF or GCD of the three numbers is 4, Highest Common Factor i.e 2^2. Hence we will require 5 rows of Banana, 3 rows of Apple and 6 rows of Mango trees. (Divide each number with 4, because each row will contain 4 trees). So total 14 rows.

Methods to Find HCF:
1) Factorization:
Express the given number in prime factor, then take the product of all the common factors, as we have done in the above example. Voila! You got your HCF.

2) Division Method:
Suppose you have two numbers, divide the greater number with the smaller one, now divide the smaller number with the remainder left, now divide the previous remainder with the new remainder, repeat this until there is no remainder. The last divisor is the required HCF.
Example: Find HCF of 12 and 15. Hence the HCF of 12 and 15 is 3.

To find HCF of more than two numbers, choose any two, find their HCF, then HCF of this HCF and other number will give you the HCF of three numbers and so on.