Best Methods to Find Highest Common Factor (H.C.F)

The H.C.F. of two or more than two numbers is the greatest number that divides each of them exactly. It is also called Greatest Common Measure (G.C.M.) and Greatest Common Divisor (G.C.D).

Methods to Find Highest Common Factor (H.C.F)

1. Factorization Method:

Break the each one of the given numbers as the product of prime factors. The product of least powers of common prime factors gives H.C.F.

Example: Find the H.C.F. of 42 and 10 ?

42 = 2×3×7

10 = 2×5

HCF will be 2

2. Division Method:

In division method, divide the larger number by the smaller number. 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 required H.C.F.

Example: Find the H.C.F. of 12 and 56 ?

Example: Find the H.C.F. of 27 and 36

Step1: Divide 36/27 , Remainder =9

Step 2: Divide dividend by remainder

27/9 , remainder = 0

Step3: So H.C.F of 27 and 36 will be = 9

3. Euclidean Algorithm Method:

This Algorithm is based on subtraction

Example : Find the Highest Common Factor of 60 and 84

                     x                y

                    60               84

Reduced the large number (y) by subtracting the smaller number (x)

                  60                84-60 = 24

Repeat        60-24 =36    24

Repeat        36-24 =12    24

Repeat        12                24-12= 12

Now here both the number becomes equal so stop here

And H.C.F. will be 12

4. Trick Method #1:

Find the H.C.F. of 60 and 84

60    84

4   15    21

3   5      7

Write down the two numbers, then (as example above) write down any common factor. I’ve chosen 4. Now divide 60 and 84 by 4 and write the answers underneath (15 and 21 in this case). Keep repeating this process until the two numbers have no common factors (as 5 and 7 above). Now, your Highest Common Factor(H.C.F.) is simply the product of numbers on the left column And for the Lowest Common Multiple (L.C.M.) find the product of the numbers on the left and the numbers in the bottom row (to find the LCM, look for the L shape).

H.C.F. = 4×3 = 12

L.C.M. = 4×3×5×7= 420

5. Trick Method #2:

Write each number as the product of its prime factors in index form.
Put a bracket around the highest power of each prime. Multiply the bracket numbers to get the LCM and multiply the non-bracket numbers to get the HCF.

Example: Find the H.C.F. of 24 and 36