Lesson 27 – GCD and LCM
Greatest Common Divisor (GCD)
The greatest common divisor, 𝑐, of two integers 𝑎 and 𝑏 is the highest integer that divides them.
It can be expressed as
𝐺𝐶𝐷(𝑎, 𝑏) = 𝑐
For Example,
the factors of 12 are 1, 2, 3, 4, 6 and 12.
the factors of 15 are 1, 3, 5 and 15.
Thus, 𝐺𝐶𝐷(12, 15) = 3
Relatively Prime Numbers
Two integers are relatively prime if their only common factor is 1. For example, 𝐺𝐶𝐷 (4 , 9) = 1,
therefore, 4 and 9 are relatively prime.
Lowest Common Multiple (LCM)
Suppose 𝑝 and 𝑞 are positive integers. Then their lowest common multiple, 𝑟, is the smallest
positive integer that is a multiple of them both. It can be expressed as
𝐿𝐶𝑀(𝑝, 𝑞) = 𝑟
For example, list the multiples of 6 and 7
6, 12, 18, 24, 30, 36, 𝟒𝟐, 48, 54, 60, 66, 72, 78, 𝟖𝟒, 90, 96, …
7, 14, 21, 28, 35, 𝟒𝟐, 49, 56, 63, 70, 77, 𝟖𝟒, 91, 98 ,105, …
Observe that 42 and 84 are both common multiples of 6 and 7. Since 42 is smaller than 84, then
𝐿𝐶𝑀(6,7) = 42.
1 © Tutify Education
Example 1
Find the lowest common multiple (LCM) of 24 and 90.
Method 1: Prime Factorisation
Method 2: The Ladder Method
2 © Tutify Education
Practice
1. Evaluate the following.
a) 𝐿𝐶𝑀(192, 180)
b) 𝐿𝐶𝑀(492, 375)
c) 𝐿𝐶𝑀(1119, 64)
3 © Tutify Education
Example 2
Find the Greatest Common Divisor (GCD) / Highest Common Factor (HCF) of 24 and 90.
Method 1: Prime Factorisation
Method 2: The Ladder Method
4 © Tutify Education
Practice
2. Evaluate the following.
a) 𝐺𝐶𝐷(382,573)
b) 𝐻𝐶𝐹(32, 800)
c) 𝐺𝐶𝐷(1800, 1260)
5 © Tutify Education
3. What is the largest prime factor of 2310?
4. How many whole numbers less than 400 are divisible by 17 or 23?
6 © Tutify Education
5. There were three traffic lights A, B and C. They turn red every 3, 5 and 12 minutes,
respectively. Given that the traffic lights were all red at 10:00 AM, when will they next
turn red together?
6. Find two numbers between 100 and 150 with a HCF of 24.
7 © Tutify Education
7. Find the smallest number between 200 and 500, which leaves a remainder of 3 when
divided by 8, 10, 12 or 30.
8. Find the smallest 4-digit number, which when divided by 40,50 or 60, leaves a
remainder of 5.
8 © Tutify Education
Example 3
When 152 is divided by 𝑛, the remainder is 8. How many possible values of 𝑛 are there?
Practice
9. Find the sum of all factors of 72.
9 © Tutify Education
10. Find the smallest number that has exactly 10 factors.
11. Find the numbers between 300 and 500 that have an odd number of factors.
10 © Tutify Education
