HCF Calculator — Highest Common Factor (GCD) of 2-5 Numbers
Calculate the Highest Common Factor (HCF) or Greatest Common Divisor (GCD) of up to 5 numbers. Shows prime factorization and Euclidean algorithm steps.
Examples:
—
HCF / GCD
—
Coprime?
Step-by-Step Solution
Euclidean Algorithm Example
GCD(48, 18):
- 48 = 2 × 18 + 12 → GCD(18, 12)
- 18 = 1 × 12 + 6 → GCD(12, 6)
- 12 = 2 × 6 + 0 → GCD = 6
Frequently Asked Questions
What is HCF (Highest Common Factor)?
The Highest Common Factor (HCF), also called GCD (Greatest Common Divisor), is the largest positive integer that divides all given numbers without remainder. For example, HCF(12, 18) = 6, since 6 is the largest number that divides both 12 and 18.
What is the Euclidean algorithm?
The Euclidean algorithm finds GCD efficiently: GCD(a, b) = GCD(b, a mod b), repeated until the remainder is 0. For example: GCD(48, 18) = GCD(18, 12) = GCD(12, 6) = GCD(6, 0) = 6.
How does HCF relate to LCM?
For two numbers a and b: HCF(a,b) × LCM(a,b) = a × b. So if you know HCF, you can quickly find LCM: LCM = (a × b) / HCF.
What is HCF used for?
HCF is used to simplify fractions (divide numerator and denominator by HCF), to solve problems about dividing things into equal groups, and in cryptography (RSA algorithm uses GCD).
What is a coprime (relatively prime) pair?
Two numbers are coprime if their HCF = 1. For example, 8 and 15 are coprime (HCF = 1) even though neither is prime. Consecutive integers are always coprime.