Greatest Common Divisor
Every question with a fully worked solution.
- Greatest Common Divisor - Video - Greatest Common Divisor (GCD) / Greatest Common Factor (GCF) Watch
Theory
The highest common factor (HCF) of two numbers is the largest number that divides into both of them exactly. It is also called the greatest common divisor (GCD). The HCF of \(27\) and \(45\) is \(9\). This Year 7 maths page shows two methods (listing factors and prime factors) and uses the HCF to simplify fractions and to share things into equal groups.
A factor of a number divides into it exactly. A common factor of two numbers is a factor of both of them. The highest common factor (HCF), or greatest common divisor (GCD), is the largest common factor.
Method 1: list the factors. List the factors of each number in pairs, pick out the ones in both lists, then choose the largest.
Factors of \(27\): \(1, 3, 9, 27\)
Factors of \(45\): \(1, 3, 5, 9, 15, 45\)
Common factors: \(1, 3, 9\), so the HCF is \(9\).
Method 2: prime factors. Write each number as a product of primes. Match the primes that are in both numbers, then multiply the shared primes. \(36 = 2 \times 2 \times 3 \times 3\) and \(60 = 2 \times 2 \times 3 \times 5\) share \(2, 2, 3\), so the HCF is \(2 \times 2 \times 3 = 12\).
In index form, take each prime that both numbers have and use the smaller power: \(2^3 \times 5\) and \(2^2 \times 5^2\) have HCF \(2^2 \times 5 = 20\).
Check: the HCF divides both numbers exactly. If two numbers share no prime (like \(9\) and \(20\)), their HCF is \(1\). Every common factor of two numbers is a factor of their HCF.
Line up the primes. The HCF uses only the primes both numbers share:
| Number | Prime factors |
|---|---|
| \(36\) | \(2 \times 2 \times 3 \times 3\) |
| \(60\) | \(2 \times 2 \times 3 \times 5\) |
| shared | \(2,\ 2,\ 3\) |
| HCF | \(2 \times 2 \times 3 = 12\) |
How to find the HCF by listing factors
- List the factors of each number (in pairs, so none are missed).
- Circle the factors that are in both lists.
- Choose the largest one, and check it divides both numbers.
How to find the HCF with prime factors
- Write each number as a product of primes (a factor tree helps).
- Match the primes that are in both numbers, one pair at a time.
- Multiply the shared primes. In index form, use the smaller power of each shared prime.
How to spot an HCF problem
- Things are shared or cut into equal groups or pieces with nothing left over.
- You want the largest group, piece or tile: find the HCF.
- Then divide each amount by the HCF to see what is in each group.
(i) \(24\) and \(32\)
(ii) \(9\) and \(20\)
(i) Factors of \(24\): \(1, 2, 3, 4, 6, 8, 12, 24\). Factors of \(32\): \(1, 2, 4, 8, 16, 32\). Common factors: \(1, 2, 4, 8\).
(ii) Factors of \(9\): \(1, 3, 9\). Factors of \(20\): \(1, 2, 4, 5, 10, 20\). The only common factor is \(1\).
| \(24 \div 8\) | \(=\) | \(3\) |
| \(32 \div 8\) | \(=\) | \(4\) |
(i) \(8\)
(ii) \(1\)
| \(3 \times 5 \times 7\) | \(=\) | \((3 \times 5) \times 7\) |
| \(3 \times 5 \times 11\) | \(=\) | \((3 \times 5) \times 11\) |
| \(\text{GCD}\) | \(=\) | \(3 \times 5 = 15\) |
The GCD is \(15\).
(i) \(24\) and \(40\)
(ii) \(90\) and \(126\)
| \(24\) | \(=\) | \(2 \times 2 \times 2 \times 3\) |
| \(40\) | \(=\) | \(2 \times 2 \times 2 \times 5\) |
| \(90\) | \(=\) | \(2 \times 3 \times 3 \times 5\) |
| \(126\) | \(=\) | \(2 \times 3 \times 3 \times 7\) |
| \(2 \times 3 \times 3\) | \(=\) | \(18\) |
(i) Shared primes \(2, 2, 2\): HCF \(= 8\).
(ii) Shared primes \(2, 3, 3\): HCF \(= 18\). Check: \(90 \div 18 = 5\) and \(126 \div 18 = 7\).
\(56 = 2 \times 2 \times 2 \times 7\) and \(84 = 2 \times 2 \times 3 \times 7\). Shared primes: \(2, 2, 7\), so the HCF is \(28\).
| \(\dfrac{56}{84}\) | \(=\) | \(\dfrac{56 \div 28}{84 \div 28}\) |
| \(\) | \(=\) | \(\dfrac{2}{3}\) |
\(\dfrac{56}{84} = \dfrac{2}{3}\) in one step.
(i) What is the greatest number of packs?
(ii) What is in each pack?
The number of packs must divide \(48\) and \(80\), and be as large as possible: the HCF. \(48 = 2^4 \times 3\) and \(80 = 2^4 \times 5\), so the HCF is \(2^4 = 16\).
| \(48 \div 16\) | \(=\) | \(3\) |
| \(80 \div 16\) | \(=\) | \(5\) |
(i) \(16\) packs
(ii) \(3\) muesli bars and \(5\) apples in each pack
(i) What is the largest possible tile?
(ii) How many tiles are needed?
The side of the tile must divide \(120\) and \(280\). \(120 = 2^3 \times 3 \times 5\) and \(280 = 2^3 \times 5 \times 7\), so the HCF is \(2^3 \times 5 = 40\).
| \(120 \div 40\) | \(=\) | \(3\) |
| \(280 \div 40\) | \(=\) | \(7\) |
| \(3 \times 7\) | \(=\) | \(21\) |
(i) \(40\) cm by \(40\) cm (see Diagrams)
(ii) \(21\) tiles
(ii) The HCF of \(21\) and a number \(n\) is \(7\). The number \(n\) is between \(50\) and \(60\). Find \(n\).
(i) Use the smaller power of each shared prime: \(2^2\), \(3^1\) and \(5^1\). Every common factor is a factor of the HCF, so count the factors of \(60\): \(1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60\).
(ii) \(n\) must be a multiple of \(7\). The only one between \(50\) and \(60\) is \(56\).
| \(2^2 \times 3 \times 5\) | \(=\) | \(60\) |
(i) HCF \(= 2^2 \times 3 \times 5 = 60\), and they have \(12\) common factors.
(ii) \(n = 56\). Check: \(21 = 3 \times 7\) and \(56 = 2 \times 2 \times 2 \times 7\) share only \(7\), so the HCF is \(7\).
Common pitfalls
Frequently asked questions
What is the highest common factor?
The largest number that divides exactly into both numbers. It is also called the greatest common divisor (GCD).
How do you find the HCF with prime factors?
Write both numbers as products of primes and multiply the primes they share. \(36\) and \(60\) share \(2 \times 2 \times 3\), so the HCF is \(12\).
What is the HCF of two numbers that share no primes?
It is \(1\). For example, the HCF of \(9\) and \(20\) is \(1\).
How is the HCF used to simplify a fraction?
Divide the top and the bottom by the HCF. The HCF of \(56\) and \(84\) is \(28\), so \(\dfrac{56}{84} = \dfrac{2}{3}\).
How do I know a word problem needs the HCF?
Look for sharing or cutting into the largest equal groups, pieces or tiles with nothing left over.