HIGHEST COMMON FACTOR

As we know H.C.F. stands for highest common factor.

HCF

Let us first discuss about factors.

Factors: When two or more natural numbers are multiplied together, the result is referred as their product, and each of the numbers multiplied is called a factor of this product.

For example: product of 3 and 7 is 21, therefore 3 and 7 are factors of 21, product of 2, 3 and 5 is 30, therefore each of 2, 3 and 5 is a factor of 30.

In other words

Any natural number that divides a given number completely is called a factor of the given number.

For example: 5 divides 20 completely → 5 is a factor of 20,

                       7 divides 42 completely → 7 is a factor of 42.

As each of 1, 2, 3, 4, 6, 8, 12 and 24 divides 24 completely, so factors of 24 are 1, 2, 3, 4, 6, 12 and 24. 

Factors of F24 = 1, 2, 3, 4, 6, 12, 24.

• 1 (one) is a factor of every number.
• Every number is a factor of itself.
• Zero (0) can not be a factor of any number.

Prime factors: Any prime number that divides completely a given natural number is called a prime factor of the given number.

For example: factors of 24 are 1, 2, 3, 4, 6, 12 and 24. Out of these 2 and 3 are the prime numbers and so the factors 2 and 3 are called the prime factors of 24.

HIGHEST COMMON FACTOR: The H.C.F. of two or more given numbers is the greatest number that divides each of the given numbers.

For example: The greatest number that can divide both 18 and 24 completely is 6; therefore, H.C.F. of 18 and 24 = 6.

METHODS OF FINDING H.C.F.

For finding the H.C.F. of two or more given numbers, any of the following three methods can be used: 

1) Common Factor Method: 

Step 1: Firstly find all the possible factors of each given number. 

Step 2: From the factors obtained in Step 1, select the common factors.

Step 3: Out of the common factors, obtained in Step 2, take the highest factor, which is the Highest Common Factor (H.C.F.) of the given numbers.

For example:

Step 1: Factors of 36 = 1, 2, 3, 4, 6, 9, 12, 18, 36 and

            Factors of 48 = 1, 2, 3, 4, 6, 8, 12, 16, 24, 48.

Step 2: Factors that are common to 36 and 48 = 1, 2, 3, 4, 6, 12

Step 3: From the result of Step 2, the highest common factor = 12

2) Prime factor method: 

Step 1: Split each given number into its prime factors.

Step 2: Select the common prime factors.

Step 3: Multiply the prime factors obtained in Step 2.

The product so obtained is the H.C.F. of the given numbers.

For example: Find H.C.F. of 15 and 25.

Step 1: Prime factors of 15 are 3 and 5, since 5 × 3 = 15, prime factors of 25 are 5 and 5, since 5 × 5 = 25

Step 2: Since the common prime factor is 5 only,

 Step 3: Therefore H.C.F. of 15 and 25 is 5.

 Any two numbers that do not have a common prime factor are called co-prime numbers. e.g 2 and 3, 5 and 7.

The H.C.F. of two co-prime numbers is always 1.

3) Division method: 

Step 1: Divide the greater number by the smaller number.

Step 2: By the remainder of division in Step 1, divide the smaller number.

Step 3: By the remainder in Step 2, divide the remainder obtained in Step 1.

Step 4: Continue in the same way till no remainder is left. The last divisor is the required H.C.F.

For example: Find the H.C.F. of 36 and 60.

Step 1: 60 = 36 × 1 + 24

Step 2: 36 = 24 × 1 + 12

Step 3: 12 = 12 × 2 + 0

Since the last divisor is 12, therefore H.C.F. is 12.