Highest common factor (HCF)

The highest (greatest) common factor is the biggest common factor of two or more numbers.

Examples:
1. Calculate the highest common factor of 12 and 15:
fact (12) = {1, 2, 3, 4, 6, 12}      fact (15) = {1, 3, 5, 15}
common factors (12, 15) = {1,3};   hcf (12, 15) = 3

2. Calculate the highest common factor of 20 and 30
fact (20) = {1, 2, 4, 5, 10, 20}      
fact (30) = {1, 2, 3, 5, 6, 10, 15, 30}
common factors (20, 30) = {1, 2, 5, 10};   
hcf (20, 30) = 10

The optimum way in this case is:
- Decompose all numbers in prime factors.
- Multiply only the common factors to the minimum index.

NOTE: If there isn't a common factor, the hcf is 1. In this case, we call them coprimes.

Examples:
1. Calculate the highest common factor of 20 and 30
20 = 2² ·       5
30 = 2  ·  3  · 5        hcf (20, 30) = 2 · 5 = 10

2. Calculate the highest common factor of 150 and 225
150 = 2 · 3 ·  5²
225 =     3² · 5²    hcf (150, 225) = 3 · 5² = 75

3. Calculate the highest common factor of 8 and 9
8 =  2³            hcf (8, 9) = 1
9 =       3²        8 and 9 are coprimes

 

Exercise.- Calculate the HCF of:

a) 12 and 15

b) 11 and 12

c) 6, 8 and 12

 

 

Solutions: a)  3; b) 1 (coprimes); c) 2