HCF , Highest Common Factor

The HCF (or GCD , Greatest Common Divisor) of two numbers is the largest number that divides both of them with no remainder.

Idea

Example: HCF of $12$ and $18$. The common factors are $1, 2, 3, 6$. Largest is $6$. So $\text{HCF}(12, 18) = 6$.

Method 1: Listing factors. Write all factors of each number; find the greatest common one. Works for small numbers.

Method 2: Prime factorisation. Write each number as product of primes. For each prime, take the lower power. Multiply these.

Example: $12 = 2^2 \times 3$ and $18 = 2 \times 3^2$. Common primes: $2$ and $3$. Lower powers: $2^1$ and $3^1$. HCF $= 2 \times 3 = 6$.

Method 3: Euclidean algorithm. A fast way for large numbers.

To find $\text{HCF}(a, b)$ with $a \geq b$:

1. Divide $a$ by $b$. Let $r$ be the remainder.
2. If $r = 0$, then $b$ is the HCF.
3. Otherwise, replace $a$ by $b$ and $b$ by $r$. Repeat.

Example: $\text{HCF}(84, 60)$. $84 \div 60 = 1$ R $24$. Now $\text{HCF}(60, 24)$. $60 \div 24 = 2$ R $12$. Now $\text{HCF}(24, 12)$. $24 \div 12 = 2$ R $0$. So HCF $= 12$.

The Euclidean method is fast because each step reduces the numbers; it stops in just a few steps even for very large inputs.

Using HCF. To simplify a fraction $\tfrac{a}{b}$, divide both by $\text{HCF}(a, b)$. So $\tfrac{84}{60}$ becomes $\tfrac{7}{5}$ after dividing by $12$.

Worked examples

Example 1. Find $\text{HCF}(24, 36)$ by listing.

Factors of $24$: $1,2,3,4,6,8,12,24$. Factors of $36$: $1,2,3,4,6,9,12,18,36$. Common: $1,2,3,4,6,12$. Largest: $12$.

Example 2. Find $\text{HCF}(36, 60)$ by prime factorisation.

$36 = 2^2 \times 3^2$ and $60 = 2^2 \times 3 \times 5$. Lower powers: $2^2$ and $3^1$. HCF $= 4 \times 3 = 12$.

Example 3. Find $\text{HCF}(105, 70)$ by Euclidean algorithm.

$105 \div 70 = 1$ R $35$. $70 \div 35 = 2$ R $0$. HCF $= 35$.

Example 4. Simplify $\tfrac{48}{72}$ using HCF.

$\text{HCF}(48, 72) = 24$. So $\tfrac{48}{72} = \tfrac{2}{3}$.

Try it yourself

1. $\text{HCF}(15, 25)$.
2. $\text{HCF}(28, 42)$ by prime factorisation.
3. $\text{HCF}(84, 56)$ by Euclidean method.
4. Simplify $\tfrac{72}{96}$.
5. $\text{HCF}(9, 16)$. (Hint: coprime?)
6. $\text{HCF}(120, 96)$ , any method.
7. Two numbers have HCF $1$ , what is that called?
8. Find $\text{HCF}(0, 5)$. (Convention: HCF involving $0$ equals the other number.)

Activity

Pick two of your favourite numbers. Find HCF using all three methods. Verify they give the same answer.