# 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^{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^{2}

225 = 3^{2} · 5^{2} hcf (150, 225) = 3 · 5^{2} = 75

3. Calculate the highest common factor of 8 and 9

8 = 2^{3} hcf (8, 9) = 1

9 = 3^{2} 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

Licensed under the Creative Commons Attribution Non-commercial Share Alike 3.0 License