📐 📐 HCF Calculator: How to Find Highest Common Factor (GCD)

The Highest Common Factor (HCF) — also called the Greatest Common Divisor (GCD) or Greatest Common Factor (GCF) — is the largest number that divides two or more given numbers without leaving a remainder. It is essential for simplifying fractions, solving ratio problems, and a wide range of number theory applications. The Euclidean algorithm for finding the GCD is one of the oldest algorithms in mathematics, dating back over 2,300 years.

What is HCF/GCD?

The HCF of two numbers is the largest factor common to both.

• Factors of 12: 1, 2, 3, 4, 6, 12
• Factors of 18: 1, 2, 3, 6, 9, 18
• Common factors: 1, 2, 3, 6
• HCF(12, 18) = 6 — the largest common factor

Method 1: Prime Factorization

Step 1: Find the prime factorization of each number.
Step 2: Identify prime factors that appear in ALL numbers.
Step 3: Take the LOWEST power of each common prime.
Step 4: Multiply these together.

Example: HCF(36, 48)

• 36 = 2² × 3²
• 48 = 2⁴ × 3
• Common primes: 2 (lowest power: 2²) and 3 (lowest power: 3¹)
• HCF = 2² × 3 = 4 × 3 = 12

Verify: 36 ÷ 12 = 3 ✓ and 48 ÷ 12 = 4 ✓ — both divide evenly.

Example: HCF(60, 84, 108)

• 60 = 2² × 3 × 5
• 84 = 2² × 3 × 7
• 108 = 2² × 3³
• Common to ALL: 2² and 3¹ (3 appears in all but lowest power is 3¹)
• HCF = 4 × 3 = 12

Method 2: The Euclidean Algorithm (Most Efficient)

The Euclidean algorithm is the fastest method for finding GCD, particularly for large numbers. The key insight: GCD(a, b) = GCD(b, a mod b).

Algorithm: Divide the larger by the smaller; replace the larger with the smaller, and the smaller with the remainder. Repeat until the remainder is 0 — the last non-zero divisor is the GCD.

Example: GCD(252, 105)

• 252 ÷ 105 = 2 remainder 42 → now find GCD(105, 42)
• 105 ÷ 42 = 2 remainder 21 → now find GCD(42, 21)
• 42 ÷ 21 = 2 remainder 0 → GCD = 21

Verify: 252 ÷ 21 = 12 ✓ and 105 ÷ 21 = 5 ✓

Example: GCD(48, 18)

• 48 ÷ 18 = 2 remainder 12
• 18 ÷ 12 = 1 remainder 6
• 12 ÷ 6 = 2 remainder 0 → GCD = 6

Method 3: Division Method (Suitable for Exams)

Divide both numbers by their smallest common prime factor, then continue until the results share no common factor:

HCF(24, 36):

• Both divisible by 2: 24→12, 36→18
• Both divisible by 2: 12→6, 18→9
• Both divisible by 3: 6→2, 9→3
• 2 and 3 share no common factor → stop
• HCF = 2 × 2 × 3 = 12

Real-World Applications

Simplifying Fractions

Divide both numerator and denominator by their GCD to simplify:

36/48: GCD(36, 48) = 12 → 36/12 = 3, 48/12 = 4 → 3/4

Dividing into Equal Groups

You have 48 apples and 72 oranges to pack into identical baskets, with each basket containing the same number of each fruit. What is the maximum number of baskets?

GCD(48, 72) = 24 → 24 baskets, each with 2 apples and 3 oranges

Tiling Problems

A floor measuring 180 cm × 252 cm is to be tiled with identical square tiles (no cutting). The largest tile size = GCD(180, 252) = 36 cm.

Gear Design

GCD is used in gear ratio design to find the simplest ratio between two gears and identify how many rotations before they return to their starting alignment.

Key Properties of HCF/GCD

• HCF(a, b) × LCM(a, b) = a × b (valid for two numbers)
• HCF(a, b) = HCF(b, a mod b) — basis of Euclidean algorithm
• HCF of co-prime numbers = 1: HCF(9, 25) = 1
• HCF of a number with itself = the number: HCF(15, 15) = 15
• HCF is always ≤ the smallest of the given numbers