What is HCF/GCD?
HCF (Highest Common Factor), also known as GCD (Greatest Common Divisor), is the largest positive integer that divides all the given numbers without leaving a remainder. It represents the greatest number that is a factor of all the given numbers.
Quick Example: HCF of 24 and 36
Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
Common factors: 1, 2, 3, 4, 6, 12 → HCF = 12
HCF vs LCM: Key Differences
HCF (Highest Common Factor)
- Largest number that divides all given numbers
- Also called GCD (Greatest Common Divisor)
- HCF ≤ smallest number
- Uses minimum powers of common primes
HCF(12, 18) = 6
LCM (Least Common Multiple)
- Smallest number divisible by all given numbers
- Also called LCD when working with fractions
- LCM ≥ largest number
- Uses maximum powers of all primes
LCM(12, 18) = 36
Methods to Find HCF
1. Prime Factorization Method
Find prime factorization of each number
Break down each number into prime factors.
Identify common prime factors
Find primes that appear in ALL factorizations.
Take minimum power of each common prime
Use the lowest exponent for each common prime.
Example: HCF(48, 72)
2. Division Method
Repeatedly divide all numbers by common prime factors until no common factor remains.
Example: HCF(24, 36)
| 2 | 24 | 36 |
| 2 | 12 | 18 |
| 3 | 6 | 9 |
| 2 | 3 |
3. Euclidean Algorithm
An efficient method using repeated division. Divide larger by smaller and take remainder, repeat until remainder is 0.
Divide the larger number by the smaller, note the remainder
Replace larger with smaller, smaller with remainder
Repeat until remainder = 0. The last non-zero value is HCF
Example: HCF(48, 18)
Important Relationships
HCF × LCM Formula
For two numbers a and b:
HCF(a,b) × LCM(a,b) = a × b
Coprime Numbers
Numbers with HCF = 1 are coprime (e.g., 8 and 15).
They share no common factors except 1.
HCF of Consecutive Numbers
HCF of any two consecutive integers is always 1.
HCF(n, n+1) = 1
Divisibility Property
If HCF(a, b) = d, then:
a = d × m, b = d × n where HCF(m, n) = 1
Applications of HCF
Simplifying Fractions
Divide numerator and denominator by their HCF to get the simplest form: 24/36 = 24÷12 / 36÷12 = 2/3
Equal Division Problems
Finding the largest size to divide items equally. HCF tells you the maximum group size.
Tile/Flooring Problems
Finding the largest square tile that fits perfectly. HCF of dimensions gives the tile size.
Cryptography (RSA)
The Euclidean algorithm is used in RSA encryption to find modular multiplicative inverses.
Quick Tips for Finding HCF
- If one number divides another, the smaller number is the HCF
- HCF of consecutive numbers is always 1
- If numbers are coprime (no common factors), HCF = 1
- HCF(a, 0) = a for any number a
- For large numbers, use Euclidean algorithm — it's most efficient