What is Greatest Common Factor (GCF) — Definition & Methods

TL;DR

The Greatest Common Factor (GCF) — also called Highest Common Factor (HCF) or Greatest Common Divisor (GCD) — of two or more integers is the largest positive integer that divides each of them without remainder. This article gives the formal definition, walks through three methods to find it, distinguishes GCF from LCM, shows three worked examples, and clears up the most common mistakes.

The GCF is the largest of all the common factors — the highest number that appears in both lists.

The Formal Definition of GCF

The Greatest Common Factor (GCF) of two or more positive integers is the largest positive integer that divides each of them without leaving a remainder. It's also called:

• HCF — Highest Common Factor (common in UK and Indian textbooks)
• GCD — Greatest Common Divisor (common in advanced mathematics)

Three names, one definition. The GCF of 12 and 18 is denoted gcd(12, 18) = 6.

If two numbers have a GCF of 1, they are called coprime (or relatively prime) — they share no factor larger than 1. gcd(8, 15) = 1, so 8 and 15 are coprime.

Quick reference.

• Definition: largest positive integer dividing two or more numbers.
• Notation: gcd(a,b) or HCF(a,b).
• Common factor of 1: every two integers share 1 as a factor, but the GCF is the greatest common factor — never less than 1 for positive integers.
• Coprime: gcd(a,b) = 1.
• GCF and LCM relation: gcd(a,b) × lcm(a,b) = a × b.
• Grade introduced: CCSS-M 6.NS.B.4 (GCF and LCM); NCERT Class 6 Chapter 3 — Playing with Numbers.

Method 1 — Listing Factors

The straightforward approach. List every factor of each number, then pick the biggest one they share.

To find gcd(24, 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.
• Greatest: 12.

Works well for small numbers (under ∼50). For larger numbers, listing every factor takes too long — use one of the other two methods.

Method 2 — Prime Factorisation

The most popular school method. Factor each number into primes, then take the common prime factors with the lowest power.

To find gcd(48, 60):

• 48 = 2^4 × 3.
• 60 = 2^2 × 3 × 5.
• Common prime factors: 2 (lowest power 2^2) and 3 (lowest power 3^1). Multiply:
• gcd(48, 60) = 2^2 × 3 = 4 × 3 = 12.

Why this works: a factor of both numbers must use only primes that both numbers contain, and at most the power that the lesser number contains.

Method 3 — Euclidean Algorithm

The fastest method for large numbers — the algorithm Euclid (c. 300 BCE) gave in Book VII of his Elements.

The trick: gcd(a,b) = gcd(b, a mod b). Replace the larger number with the remainder, repeat until the remainder is 0. The last nonzero remainder is the GCF.

To find gcd(252, 105):

• 252 = 2 × 105 + 42. So gcd(252, 105) = gcd(105, 42).
• 105 = 2 × 42 + 21. So gcd(105, 42) = gcd(42, 21).
• 42 = 2 × 21 + 0. So gcd(42, 21) = 21.
• gcd(252, 105) = 21.

The algorithm finishes in O(log n) steps — fast even for 20-digit numbers used in RSA cryptography.

GCF vs LCM — The Easy Confusion

For 12 and 18: gcd × lcm = 6 × 36 = 216 = 12 × 18 ✓. Two numbers, two summary statistics.

Three Worked Examples Of GCF — Quick, Standard, Stretch

Quick. Find gcd(8,12).

• Factors of 8: 1, 2, 4, 8. Factors of 12: 1, 2, 3, 4, 6, 12. Common: 1, 2, 4. Greatest: 4.
• Final answer: gcd(8,12) = 4.

Standard (Wrong Path First — Where Students Lose the Mark). Find gcd(36,54) using prime factorisation.

• The wrong path: factors:
  • 36 = 2^2 × 3^2. 54 = 2 × 3^3.
• Common primes: 2^2 and 3^3. So gcd = 4 × 27 = 108.
• The flaw: 108 is bigger than 54 — and a common factor can't be bigger than the smaller number. Taking the highest power gives the LCM, not the GCF.
• The correct way: For GCF, take the lowest power of each common prime:
  • 2: lowest power is 2^1.
  • 3: lowest power is 3^1.
• gcd(36,54) = 2 × 3^2 = 2 × 9 = 18.
• Final answer: gcd(36,54) = 18.

Stretch. Find gcd(144,96) using the Euclidean algorithm.

• 144 = 1 × 96 + 48. gcd(144,96) = gcd(96,48).
• 96 = 2 × 48 + 0. gcd(96,48) = 48.
• Final answer: gcd(144,96) = 48.

Cross-check by prime factorisation: 144 = 2^4 × 3^2, 96 = 2^5 × 3. Lowest powers: 2^4 × 3^1 = 16 × 3 = 48 ✓.

Where GCF Appears — Beyond the Worksheet

A few places this idea quietly does work:

• Simplifying fractions. (\frac{18}{24} = \frac{18 \div 6}{24 \div 6} = \frac{3}{4}).
• Cryptography. RSA encryption relies on the difficulty of finding the GCF of very large numbers.
• Music theory. Two musical rhythms played together return to sync after a number of beats equal to the LCM of their periods.
• Engineering. The GCF of tooth counts of two gears determines how many full rotations until the same teeth meet again.

Tripping Points to Avoid With GCF

Mistake 1: Taking the highest power instead of the lowest (in prime factorisation)

• Where it slips in: gcd(36,54) computed as 108.
• Don't do this: Treat GCF and LCM the same in the prime-factor approach.
• The correct way: For GCF, take the lowest power of each common prime. For LCM, take the highest.

Mistake 2: Confusing GCF with LCM

• Where it slips in: A problem asks for the smallest common multiple; student gives the largest common factor.
• Don't do this: Use the GCF formula when the LCM is wanted.
• The correct way: Read the question carefully. Factor / divisor → GCF. Multiple → LCM.

Mistake 3: Forgetting the GCF of coprime numbers is 1

• Where it slips in: gcd(8,15) — student says "they have no common factor."
• Don't do this: Say "no GCF" when no common factor above 1 exists.

Conclusion

• The GCF (HCF, GCD) is the largest positive integer dividing two or more numbers without remainder.
• Three methods: listing factors, prime factorisation with lowest powers, Euclidean algorithm (large numbers).
• GCF is at most the smaller number; the LCM is at least the larger.
• Two coprime numbers have GCF = 1 — they share no factor greater than 1.
• gcd(a,b) × lcm(a,b) = a × b — a clean two-way identity.
• The most common mistake is taking the highest power instead of the lowest in prime factorisation.

Quick Self-Check — Three Problems

1. Find gcd(15,20) by listing factors.
2. Find gcd(72,108) by prime factorisation.
3. Find gcd(176,130) using the Euclidean algorithm.