Greatest Common Divisor (GCD/HCF)
Numbers · Greatest Common Divisor
Syllabus tag: KCSE | Mathematics | Form 1 | Topic 4 Greatest Common Divisor (GCD/HCF)
Lesson objectives
By the end of this topic, you should be able to:
- Find the GCD of a set of numbers by listing factors.
- Find the GCD using prime factorisation.
- Apply the GCD to real life situations.
- Distinguish clearly between GCD and LCM problems.
Greatest Common Divisor (GCD/HCF)
The GCD of two or more numbers is the largest number that divides into all of them exactly.
It is also called the HCF, the highest common factor. The two names mean the same thing.
a) By listing factors
List every factor of each number.
Find the ones that appear in all the lists.
The largest of those is the GCD.
This method is clear but slow for large numbers.
b) By prime factorisation
Write each number as a product of primes in index form.
Take only the primes that appear in every number.
Take each at its lowest power.
Multiply those together.
c) Why the lowest power
The GCD must divide into both numbers.
Since 36 has only 2², the GCD cannot contain 2³ or more, even though 48 does.
The lower power is the most that both can supply. That is the whole reason for the rule.
d) Three or more numbers
The method is unchanged. A prime must appear in every factorisation to count.
For 24, 36 and 60: these are 2³×3, 2²×3² and 2²×3×5. Only 2 and 3 appear in all three. The lowest powers are 2² and 3. So the GCD is 12.
The 5 is ignored, because it appears in only one of them.
e) Telling GCD from LCM problems
This is the distinction that matters most in exams.
GCD applies when you are splitting or grouping things into the largest equal parts. Cutting ribbon into the longest equal pieces. Making the largest possible identical bundles.
LCM applies when things repeat and you want them to coincide. Two buses leaving together again. Two bells ringing at the same moment.
A quick check on size. The GCD is never larger than the smallest number given. The LCM is never smaller than the largest. If your answer breaks that, you have used the wrong one.
f) A real example
Two ribbons measure 36 cm and 48 cm. They must be cut into equal pieces, as long as possible, with nothing left over.
The piece length must divide both, and be as large as possible. That is the GCD, so 12 cm.
The first ribbon gives 3 pieces, the second 4.
g) Where this is used
Simplifying fractions to lowest terms. Sharing items into the largest equal groups. Tiling a floor with the largest square tile that fits exactly.
Words to know
- GCD (HCF) -- the largest number that divides two or more numbers exactly.
- Common factor -- a factor shared by two or more numbers.
- Coprime -- having a GCD of 1, so sharing no prime factors.
- Index form -- writing a number as primes raised to powers.
- Lowest power -- the smallest index of a prime across the numbers considered.
:::checkpoint Check yourself
- Find the GCD of 18 and 30 by listing factors.
- Find the GCD of 72 and 120 by prime factorisation.
- Why do you take the lowest power of each shared prime?
- Is the GCD ever larger than the smallest number given? :::
Bridge to practice
The exercises begin with the meaning of the GCD and the listing method, move through prime factorisation and coprime numbers, and finish with word problems and the GCD-LCM relationship. For every word problem, decide first whether you are breaking down or building up before doing any arithmetic.