School MathLive results
HCF / GCD Calculator
Find the Highest Common Factor (Greatest Common Divisor) of two numbers.
Formula
Euclid’s algorithm
How to use
- 1Enter the two numbers.
- 2Read the HCF (GCD).
About this calculator
The highest common factor of two numbers is the largest value that divides both exactly. It goes by two names - HCF (highest common factor) and GCD (greatest common divisor) - but they mean the same thing. This tool finds it instantly using Euclid’s algorithm.
Formula explained
Euclid’s algorithm: HCF(a, b) = HCF(b, a mod b), repeated until the second number is zero. At each step the larger number is replaced by the remainder, and the last non-zero value is the HCF. It works because any common divisor of two numbers also divides their remainder.
Worked example
HCF(24, 36) → HCF(36, 24) → 36 mod 24 = 12 → HCF(24, 12) → 24 mod 12 = 0 → HCF(12, 0) = 12.
Tips & notes
- HCF × LCM = the product of the two numbers, so LCM = (a × b) ÷ HCF.
- Use the HCF to reduce fractions to lowest terms in one step.
- If one number divides the other exactly, the smaller number is the HCF.