HCF and LCM Calculator
Highest common factor (HCF) and lowest common multiple (LCM) — with Euclid's algorithm.
The HCF (Highest Common Factor, also called the GCD — Greatest Common Divisor) is the largest positive whole number that divides two (or more) numbers with no remainder. The LCM (Lowest Common Multiple) is the smallest positive number that two numbers both divide into with no remainder. The two are linked through the identity a · b = hcf(a, b) · lcm(a, b).
Euclid's algorithm — the process: divide the larger number by the smaller, replace the larger with the smaller and the smaller with the remainder, and repeat. Once the remainder is 0, the last divisor is the HCF. The method works because any common factor of two numbers also divides their remainder.
- hcf(60, 24): 60 = 2·24 + 12 → 24 = 2·12 + 0 → HCF = 12
- hcf(1071, 462): 1071 = 2·462 + 147 → 462 = 3·147 + 21 → 147 = 7·21 + 0 → HCF = 21
- lcm(12, 18) = 12·18 / hcf(12, 18) = 216 / 6 = 36
How to use it
The HCF — Highest Common Factor (also known internationally as the GCD, Greatest Common Divisor) is the largest whole number that divides all the numbers entered with no remainder. The LCM — Lowest Common Multiple is the smallest positive number that all the numbers entered divide into with no remainder.
The calculator uses Euclid's algorithm for the HCF and the formula a · b / hcf(a, b) for the LCM. It also shows the prime factorisation: the HCF is the product of the minimum power of each shared factor, and the LCM is the product of the maximum power of each factor.
- Euclid's algorithm — divide the larger by the smaller, swap, and repeat. Stop when the remainder is 0; the last divisor is the HCF.
- 3 numbers— click "+ Add another number" to enter a third one. The steps are worked out in pairs.
- Uses — simplifying fractions (HCF), finding a common denominator (LCM), working out gear rotations, syncing periodic events, and more.
Related tools
✍️ Written by the MathsUK teamChecked against the National Curriculum and GCSE specifications