Methods of finding highest common factor

Highest Common Factor (HCF) or Greatest Common Divisor (GCD):

The positive factors of 8 are: 1, 2, 4, and 8, and

The positive factors of 12 are: 1, 2, 3, 4, 6, and 12

Among the common factors of 8 and 12, 4 is the greatest factor.

4 is therefore said to be the Highest Common Factor or Greatest Common Divisor of 8 and 12.

How to Find the HCF of two or more numbers:

Example1:

Find the HCF of 18 and 24.

Solution: express both 18 and 24 as product of prime factors:

18 = 2 × 9 = 2 × 32 and

24 = 2 × 12 = 2 × 3 × 4 = 2 × 3 × 22 = 24 × 3

Now, 2 and 3 are the factors common to 18 and 24, and

Factors common to 18 and 24 are 2 and 3.

In 18 there is 2 and in 24 there is 24.

Between 2 and 24, select 2 as it is the factor common to 18 and 24 with the least power, and

In 18, there is 32 and in 24, there is 3.

Between 32 and 3, select 3, as it is the factor common to 18 and 24 with the least power.

Now HCF is product of 2 and 3, i.e. 2 × 3 = 6

Example 2:

Find the HCF of 36 and 48.

Solution:

Express both 36 and 48 as product of prime factors as below:

36 = 2 × 18 = 2 × 2 × 9 = 22 × 32, and

48 = 2 × 24 = 2 × 2 × 12 = 2 × 2 × 3 × 4 = 22 × 3 × 22 = 24 × 3

Now, the common factors of 36 and 48 are 2 and 3.

To write their HCF, first select numbers with least powers of 2 and 3.

They are: 22 and 3.

HCF is therefore, the product of numbers having least powers of common factors:

22 × 3 = 12

Example 3:

Find the HCF of 30 and 105

Solution:

30 = 2 × 15 = 2 × 3 × 5, and

105 = 3 × 35 = 3 × 5 × 7.

Now, the factors common to 30 and 105 are: 3 and 5.

Their product 3 × 5 = 15 is therefore, the HCF of 30 and 105.

Example 4:

Find the HCF of 20 and 45.

Solution:

20 = 2 × 10 = 2 × 2 × 5 = 22 × 5, and

45 = 3 × 15 = 3 × 3 × 5 = 32 × 5.

Now, the common factor of 20 and 45 is 5.

Therefore, 5 is the HCF of 20 and 45.

Example 5:

Find the HCF of 8 and 9.

Solution:

Now, 8 = 23 and 9 = 32.

We can see that 8 and 9 do not have any common factor.

But we can choose to write:

 8 as 1 × 8, and 9 as 1 × 9.

Now, 1 can be taken as the common factor of 8 and 9.

Therefore, the HCF of 8 and 9 is 1.

Example 6:

We know that the HCF of 12 and 18 is 6, and that

 12 = 6 × 2 and 18 = 6 × 3.

Here, we can see that 2 and 3 are co-primes with the only common factor 1.

Here the constant remainder is 10.