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 $\mathrm{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) \times \mathrm{lcm}(a, b) = a \times 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: $\boxed{12}$.
Works well for small numbers (under $\sim 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} \times 3$.
$60 = 2^{2} \times 3 \times 5$.
Common prime factors: $2$ (lowest power $2^{2}$) and $3$ (lowest power $3^{1}$). Multiply:
$$\gcd(48, 60) = 2^{2} \times 3 = 4 \times 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, over $2{,}300$ years ago. It's still the algorithm computers use.
The trick: $\gcd(a, b) = \gcd(b, a \bmod 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 \times 105 + 42$. So $\gcd(252, 105) = \gcd(105, 42)$.
$105 = 2 \times 42 + 21$. So $\gcd(105, 42) = \gcd(42, 21)$.
$42 = 2 \times 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 | Largest common divisor | Smallest common multiple |
For $\gcd/\mathrm{lcm}(12, 18)$ | $6$ | $36$ |
When to use | Simplifying fractions, finding common factors | Finding common denominators, scheduling problems |
Identity | $\gcd(a, b) \times \mathrm{lcm}(a, b) = a \times b$ | (same) |
For $12$ and $18$: $\gcd \times \mathrm{lcm} = 6 \times 36 = 216 = 12 \times 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. A student factors:
$36 = 2^{2} \times 3^{2}$. $54 = 2 \times 3^{3}$.
Then writes: "Common primes are $2$ and $3$. Take the highest powers — $2^{2}$ and $3^{3}$. So $\gcd = 4 \times 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 rescue. For GCF, take the lowest power of each common prime:
$2$: lowest power is $2^{1}$ (since $54$ has only $2^{1}$).
$3$: lowest power is $3^{2}$ (since $36$ has only $3^{2}$).
$$\gcd(36, 54) = 2 \times 3^{2} = 2 \times 9 = 18.$$
Verify: $18 \times 2 = 36$ ✓ and $18 \times 3 = 54$ ✓.
Final answer: $\gcd(36, 54) = 18$.
The lesson — for GCF, take the lowest power of common primes; for LCM, take the highest. Swapping these is the single most common GCF mistake.
Stretch. Find $\gcd(144, 96)$ using the Euclidean algorithm.
$144 = 1 \times 96 + 48$. So $\gcd(144, 96) = \gcd(96, 48)$.
$96 = 2 \times 48 + 0$. So $\gcd(96, 48) = 48$.
Final answer: $\gcd(144, 96) = 48$.
Cross-check by prime factorisation: $144 = 2^{4} \times 3^{2}$, $96 = 2^{5} \times 3$. Lowest powers: $2^{4} \times 3^{1} = 16 \times 3 = 48$ ✓.
This is the version of GCF problem that appears in CBSE Class 6 and CCSS-M Grade 6 number theory.
Where GCF Appears — Beyond the Worksheet
A few places this idea quietly does work:
Simplifying fractions. $\dfrac{18}{24} = \dfrac{18 \div 6}{24 \div 6} = \dfrac{3}{4}$ — the GCF $6$ is exactly the number to divide by.
Cryptography. RSA encryption relies on the difficulty of finding the GCF of two very large numbers — the Euclidean algorithm makes the easy direction tractable, while factoring keeps the hard direction secure.
Music theory. Two musical rhythms played together return to sync after a number of beats equal to the LCM of their periods, divided by the GCF.
Engineering. When two gears mesh, the GCF of their tooth counts determines how many full rotations until the same teeth meet again.
The Euclidean algorithm has remained essentially unchanged since Euclid (c. 300 BCE) — making it one of the oldest algorithms in continuous use. Later number theorists like Pierre de Fermat (1607–1665, France) and Carl Friedrich Gauss (1777–1855, Germany) built modern number theory on top of the GCF concept.
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 way 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. The GCF is at most the smaller of the two numbers; the LCM is at least the larger.
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.
The correct way: Every two positive integers share at least the factor $1$. So $\gcd(a, b) \geq 1$ always. $\gcd(8, 15) = 1$ — they are coprime, but the GCF is defined.
Conclusion
The GCF (HCF, GCD) is the largest positive integer dividing two or more numbers without remainder.
Three methods: listing factors (small numbers), prime factorisation with lowest powers (medium numbers), 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) \times \mathrm{lcm}(a, b) = a \times 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
Find $\gcd(15, 20)$ by listing factors.
Find $\gcd(72, 108)$ by prime factorisation.
Find $\gcd(176, 130)$ using the Euclidean algorithm.
If problem 2 gave $216$, return to Mistake 1 above — you took the highest power instead of the lowest.
Want a live Bhanzu trainer to walk your child through GCF, LCM, and prime factorisation? Book a free demo class — online globally.
Was this article helpful?
Your feedback helps us write better content