Find the highest common factor of two or more whole numbers — the biggest number that divides evenly into all of them. This is also called the greatest common divisor (GCD).
The larger number is divided by the smaller, and the remainder is kept.
The process repeats with the smaller number and that remainder.
When the remainder reaches zero, the last non-zero value is the HCF.
For more than two numbers, the HCF is found for the first pair and then carried forward through the list.
Euclidean algorithm: GCD(a, b) = GCD(b, a mod b)
Stop when: b = 0, then a is the GCD
Relationship: HCF × LCM = a × b
Finding the HCF of 12 and 18.
Numbers: 12, 18
18 ÷ 12 leaves a remainder of 6
12 ÷ 6 leaves a remainder of 0
The last non-zero remainder is 6
Answer: HCF = 6
An HCF calculator finds the highest common factor of two or more whole numbers, the largest number that divides all of them without a remainder. In many other countries it is called the greatest common divisor, or GCD. This calculator uses Euclid's division algorithm and shows every division, which is exactly the method taught in Class 10 NCERT real numbers.
The HCF answers practical questions about equal grouping. What is the longest ribbon length that cuts pieces of 84 cm, 126 cm and 210 cm with no waste? What is the largest tile that fits a floor exactly? How many identical kits can be made from given stocks? It is also the number you divide by to reduce a fraction to lowest terms.
1. Take the two numbers a and b with a ≥ b.
2. Divide a by b to get a = b × q + r, where r is the remainder.
3. If r = 0, then b is the HCF. Otherwise replace a with b and b with r.
4. Repeat the division until the remainder is zero; the last non-zero divisor is the HCF.
5. For more than two numbers, find the HCF of the first two, then the HCF of that result with the next number, and so on.
6. Check by dividing each original number by the answer.
If a = b × q + r, then any number that divides both a and b also divides r = a − b × q. Conversely, any number that divides b and r also divides a. So the pairs (a, b) and (b, r) have exactly the same common divisors, and therefore the same highest one. Each step keeps the HCF unchanged while making the numbers smaller. Since remainders strictly decrease, the process must reach zero, and HCF(g, 0) = g. This is Euclid's division lemma applied repeatedly.
You can also find the HCF by writing each number as a product of primes and taking every common prime to its lowest power. For 84 = 2² × 3 × 7, 126 = 2 × 3² × 7 and 210 = 2 × 3 × 5 × 7, the common primes are 2, 3 and 7, each to power 1, giving 42. Factorisation is clear for small numbers but slow for large ones, because finding prime factors is hard. Euclid's method needs only division, so it stays fast even for very large numbers.
For two numbers, HCF × LCM = a × b. This holds because the HCF takes each prime to its lower power and the LCM to its higher power, so together they use every prime power exactly once. The identity does not extend to three or more numbers. For 84, 126 and 210 the product is far larger than HCF × LCM. Numbers whose HCF is 1 are called coprime; they need not be prime themselves, like 8 and 15.
Pooja is cutting three ribbons of 84 cm, 126 cm and 210 cm into pieces of equal length for a school decoration and wants the longest piece that leaves no waste.
Find the HCF of 84 and 126: Using the Euclidean algorithm
Divide 126 by 84: 126 = 84 × 1 + 42
Divide 84 by 42: 84 = 42 × 2 + 0
HCF so far: HCF(84, 126)
Find the HCF of 42 and 210: Using the Euclidean algorithm
Divide 210 by 42: 210 = 42 × 5 + 0
HCF so far: HCF(42, 210)
Answer: HCF (highest common factor) 42; LCM (for comparison) 1260; Numbers used 84, 126, 210
Confusing HCF with LCM in word problems; equal pieces or groups need the HCF, while events that coincide need the LCM.
Using HCF × LCM = product for three or more numbers.
Stopping Euclid's algorithm one step early and reporting the last remainder instead of the last divisor.
Missing a common prime factor, or taking the higher power instead of the lower one.
Reducing fractions to lowest terms.
Finding the largest tile size that covers a rectangular floor exactly.
Packing items into the maximum number of identical kits or hampers.
Cutting rods, cloth or ribbons into the longest equal pieces without waste.
Class 10 board questions on Euclid's division lemma.
Are HCF and GCD the same thing?
Yes. 'Highest common factor' is the term used in Indian and British schools. 'Greatest common divisor' is more common in the US and in computer science. They mean exactly the same thing.
What does an HCF of 1 mean?
The numbers are called coprime — they share no common factor except 1. They do not need to be prime numbers themselves. For example, 8 and 9 are coprime, even though neither one is a prime number.
Why is the Euclidean algorithm used?
It is much faster than listing out every factor. Finding the HCF of two large numbers only takes a few divisions, which is why it has been used for over two thousand years.