FactorsHCF: highest common factor, three methods
The highest common factor (HCF) of two or more numbers is the largest number that divides all of them exactly. It is also called the greatest common divisor (GCD) or greatest common factor (GCF). All three names mean the same thing.
Method 1: listing factors
Good for small numbers. Find the HCF of 24 and 36.
- Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
- Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
- Common factors: 1, 2, 3, 4, 6, 12
The highest is 12, so HCF(24, 36) = 12.
Method 2: prime factorisation
Write each number as a product of primes. Take the primes that appear in every number, each with its smallest power, and multiply.
- 24 = 2³ × 3
- 36 = 2² × 3²
Both contain 2 and 3. The smaller power of 2 is 2², and of 3 is 3. HCF = 2² × 3 = 12.
Method 3: long division (Euclid's method)
Best for large numbers, because it needs no factorising. Divide the larger number by the smaller. Then divide the divisor by the remainder. Keep going until the remainder is 0. The last divisor is the HCF.
Find the HCF of 198 and 360:
- 360 ÷ 198 = 1, remainder 162
- 198 ÷ 162 = 1, remainder 36
- 162 ÷ 36 = 4, remainder 18
- 36 ÷ 18 = 2, remainder 0
The last divisor is 18, so HCF(198, 360) = 18. The reason this works is on the Euclid's algorithm page.
HCF of three numbers
Find the HCF of the first two, then the HCF of that answer and the third. For 24, 36 and 60: HCF(24, 36) = 12, and HCF(12, 60) = 12. With prime factors it can be done in one step: 24 = 2³ × 3, 36 = 2² × 3², 60 = 2² × 3 × 5. All three share 2² and 3, so the HCF is 12.
Facts about HCF
- The HCF is never larger than the smallest of the numbers.
- If one number divides the other, the smaller number is the HCF: HCF(8, 32) = 8.
- If the numbers share no factor except 1, the HCF is 1 and the numbers are called co-prime: HCF(8, 15) = 1.
- The HCF of two consecutive numbers is always 1.
- For two numbers, HCF × LCM equals the product of the numbers. For 24 and 36: 12 × 72 = 864 = 24 × 36.
When a question needs the HCF
Look for the words largest, greatest, maximum, or the idea of cutting or sharing things into equal parts with nothing left over.
- The longest tape that measures 24 m and 36 m exactly: HCF = 12 m.
- The largest square tile that covers a 198 cm by 360 cm floor without cutting: HCF = 18 cm.
- Simplifying a fraction: divide top and bottom by their HCF. 24/36 becomes 2/3.
More solved questions are on the word problems page. To see the working for your own numbers, use the HCF and LCM calculator.