HCF Calculator (Greatest Common Divisor)

The Highest Common Factor (HCF) — usually the Greatest Common Divisor (GCD) outside school textbooks — is the largest whole number that divides two (or more) numbers exactly, leaving no remainder. For 12 and 18 the shared factors 1, 2, 3 and 6 all divide both, and the largest is 6. The name difference is pure tradition: British-schooled maths calls it the "highest common factor"; American texts tend toward "greatest common divisor". Same number, same math.

The Euclidean algorithm

You could list every factor and pick the largest, but that becomes slow as numbers grow. Far better is the Euclidean algorithm, recorded by the Greek mathematician Euclid in his Elements around 300 BC — and still the fastest general method some 2,300 years later:

1. Divide the larger number by the smaller and note the remainder.
2. Replace the larger with the smaller, and the smaller with the remainder.
3. Repeat until the remainder is 0.
4. The last non-zero remainder is the HCF.

Worked example: HCF(12, 18)

18 ÷ 12 = 1 remainder 6
12 ÷ 6 = 2 remainder 0

The last non-zero remainder is 6, so HCF(12, 18) = 6. The calculator exposes each of these steps in its output so you can follow — and verify — every line by hand.

Why the algorithm never fails

Any divisor of two numbers also divides their difference. Replacing the larger number with the remainder therefore shrinks the problem at every step without ever discarding a common factor, so the final non-zero remainder is both a divisor of the originals and the largest one. The method needs no factorization and no guessing — which is why it has survived, essentially unchanged, for more than two millennia.

Real-world applications

• Simplifying fractions — 12/18 ÷ 6/6 = 2/3. Dividing numerator and denominator by the HCF yields lowest terms immediately.
• Fair sharing — 12 apples and 18 oranges split into 6 identical gift bags, each with 2 apples and 3 oranges.
• Tiling and cutting — the largest identical square that tiles a 12 × 18 surface is 6 × 6.
• Ratios — 12 : 18 simplifies to 2 : 3 through the HCF (see the ratio calculator).
• Scheduling — shared-cycle problems lean on the HCF's mirror partner, the LCM.

Coprime numbers

When the HCF is 1, the two numbers share no common factor at all — they are coprime (12 and 35, for instance). Coprime pairs produce irreducible fractions and underpin modular arithmetic and parts of modern cryptography, where the GCD is a load-bearing step in key mathematics.

HCF of more than two numbers

This tool takes two inputs. For three, reuse the answer: HCF(a, b, c) = HCF(HCF(a, b), c). The result can never grow as terms are added — the HCF only stays equal or shrinks.

HCF and LCM are locked together

HCF(a, b) × LCM(a, b) = a × b

Check for 12 and 18: 6 × 36 = 216 = 12 × 18. When two methods disagree, test the answer against this identity — if the product relationship fails, one of the calculations is wrong.

Common mistakes

• Starting by dividing the smaller number by the larger (harmless — the remainder is just the smaller number — but it adds a confusing line).
• Thinking you can stop when a remainder of 1 appears — the algorithm runs until the remainder is 0.
• Reporting the final quotient as the HCF — the answer is the last non-zero remainder.
• Forgetting that the HCF always divides both original numbers: 6 divides 12 and 18, so "6, check that" is a free verification.