Euclid Method
There are two clean ways to find an HCF. The first is prime factorization: break each number into primes and multiply the common primes taken to their LOWEST power. For 60 = 2²×3×5 and 84 = 2²×3×7, the shared part is 2²×3 = 12. This is intuitive but slow when numbers are large or hard to factor. The second is the Euclidean algorithm, the CAT favourite for big numbers: divide the larger by the smaller, replace the larger with the remainder, and repeat until the remainder is 0 — the last non-zero remainder is the HCF. In short, HCF(a, b) = HCF(b, a mod b). It needs no factoring, so HCF(1517, 902) falls out in three or four divisions. A key property worth memorising: HCF(ka, kb) = k × HCF(a, b), so you can pull out an obvious common factor first to shrink the numbers. The HCF can never exceed the smallest of the given numbers.
✅ Solved examples
✏️ Practice — try these, take hints as needed
📝 Topic test — 8 questions
Auto-graded with full solutions; saved to your dashboard. Use the calculator and formula sheet (top-right) any time.
Formula Reference Sheet
Core HCF rules
| Prime factorization HCF | product of each common prime raised to its LOWEST power |
|---|---|
| Euclidean algorithm | HCF(a, b) = HCF(b, a mod b), until remainder = 0 |
| HCF × LCM (two numbers) | HCF(a, b) × LCM(a, b) = a × b |
| HCF of fractions | HCF(numerators) / LCM(denominators) |
| Co-prime check | a, b are co-prime ⇔ HCF(a, b) = 1 |
CAT application formulas
| Largest tile / container | side or capacity = HCF of the given dimensions |
|---|---|
| Greatest number dividing a, b, c exactly | HCF(a, b, c) |
| Greatest number leaving same remainder r | HCF(a − r, b − r, c − r) |
| Greatest number leaving remainders r1, r2, r3 | HCF(a − r1, b − r2, c − r3) |
| HCF scales with a common factor | HCF(ka, kb) = k × HCF(a, b) |