# 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

|  | GCF | LCM |
| --- | --- | --- |
| What it means | **L** argest common **divisor** | **S** mallest common **multiple** |
| For gcd/lcm(12,18) | 6 | 36 |
| When to use | Simplifying fractions, finding common factors | Finding common denominators, scheduling problems |
| Identity | gcd(a,b) × lcm(a,b) = a × b | (same) |

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.