Greatest Common Factor (GCF, HCF or GCD): Rules, Methods, and Examples

What Is Greatest Common Factor (GCF, HCF or GCD)?

The greatest common factor (GCF) of two or more non-zero integers is the maximum integer that divides all of them evenly. Because every whole number has individual factors, comparing the complete factor sets of two numbers reveals their shared common factors. The largest number among those shared values is the greatest common factor.

Different international curricula use different standard terms for this concept:

• GCF (Greatest Common Factor): Standard term used across North America and international international baccalaureate programs.
• HCF (Highest Common Factor): Standard term used in the United Kingdom, India, Australia, and Commonwealth education systems.
• GCD (Greatest Common Divisor): Standard term used in higher algebra, computer science, and number theory.

All three terms describe the exact same mathematical value: $\text{GCF}(a,b)=\text{HCF}(a,b)=\text{GCD}(a,b)$.

For example, to find the greatest common factor of $12$ and $18$, list all positive factors for each number:

• Factors of $12$: $1,2,3,4,6,12$
• Factors of $18$: $1,2,3,6,9,18$

The shared factors belonging to both sets are $1,2,3,$ and $6$. The largest shared factor is $6$, so $\text{GCF}(12,18)=6$.

When two numbers share no positive common factor other than $1$, their GCF is $1$. Such numbers are called coprime (or relatively prime). For example, $8$ and $15$ share no common prime factors, so $\text{GCF}(8,15)=1$.

When to Use It

Finding the greatest common factor is essential whenever a problem involves partitioning quantities into equal, complete groups without any leftovers.

Common practical situations requiring GCF include:

• Simplifying Fractions: Dividing the numerator and denominator by their GCF reduces any fraction to its lowest terms in a single step. For instance, in $\frac{24}{36}$, dividing both parts by $\text{GCF}(24,36)=12$ gives $\frac{2}{3}$.
• Arranging Objects in Equal Rows or Groups: Packing items of different types (such as $48$ apples and $60$ oranges) into identical gift boxes with zero remaining items.
• Tiling Rectangular Areas: Determining the largest square tiles that can completely cover a rectangular floor without cutting any tile.
• Factoring Algebraic Expressions: Factoring out the greatest common term from polynomial expressions, such as $12x^2+18x=6x(2x+3)$.
  

Use GCF when dividing quantities into maximum equal groups with zero leftovers

Do not confuse GCF problems with problems that ask about future event alignment or repeating cycles. Problems involving synchronized events rely on common multiples rather than common factors.

Step-by-Step Method

There are three primary methods to calculate the greatest common factor: factor listing, prime factorization, and the division ladder method.

Method 1: Listing Factors

1. List all positive factors for each number in ascending order.
2. Identify all shared common factors present in all lists.
3. Select the largest factor among the shared set.
   

Method 2: Prime Factorization

1. Write the prime factorization of each number using factor trees or repeated prime division.
2. Express each prime factorization in exponent form.
3. Identify all prime bases that appear in every factorization.
4. For each shared prime base, pick the smallest exponent present across the factorizations.
5. Multiply these minimum prime powers together to get the GCF.
   

Method 3: Division Ladder Method

1. Write the given numbers side by side inside an inverted division step.
2. Divide all numbers simultaneously by a shared prime factor.
3. Write the resulting quotients directly underneath.
4. Repeat the process until the quotients share no common factor other than $1$.
5. Multiply all the common prime divisors along the left column.

Visual Worked Examples

Example 1: Finding the GCF of two two-digit numbers

Question: Find the greatest common factor of $28$ and $42$.

Method:

1. Express both numbers as products of prime factors:

• $28=2\times 2\times 7=2^2\times 7^1$
• $42=2\times 3\times 7=2^1\times 3^1\times 7^1$

1. Identify the prime bases shared by both numbers ($2$ and $7$).
2. Select the smallest exponent for each shared prime base:

• Minimum power of $2$: $2^1$
• Minimum power of $7$: $7^1$

1. Multiply these minimum prime powers together.

Answer: The greatest common factor of $28$ and $42$ is $14$.

Check: Divide both numbers by $14$: $\frac{28}{14}=2$ and $\frac{42}{14}=3$. The resulting quotients $2$ and $3$ share no common factor other than $1$, confirming $14$ is the greatest common factor.

Example 2: Finding the GCF of three numbers

Question: Calculate $\text{GCF}(24,36,60)$.

Method:

1. Set up the three numbers in a division ladder.
2. Divide all three numbers by shared prime factor $2$:

• $24÷2=12$, $36÷2=18$, $60÷2=30$

1. Divide the new quotients $(12,18,30)$ by shared prime factor $2$:

• $12÷2=6$, $18÷2=9$, $30÷2=15$

1. Divide the quotients $(6,9,15)$ by shared prime factor $3$:

• $6÷3=2$, $9÷3=3$, $15÷3=5$

1. The remaining quotients $(2,3,5)$ are prime to each other (coprime set).
2. Multiply all common prime divisors: $2\times 2\times 3=12$.

Answer: $\text{GCF}(24,36,60)=12$.

Check: $\frac{24}{12}=2$, $\frac{36}{12}=3$, $\frac{60}{12}=5$. Since $\text{GCF}(2,3,5)=1$, $12$ is correct.

Example 3: Word problem with equal distribution

Question: A store clerk has $48$ pencils and $72$ notebooks. What is the greatest number of identical gift packages the clerk can make so that every package contains the exact same number of pencils and notebooks with no items left over?

Method:

1. Identify that the maximum number of identical gift packages is given by $\text{GCF}(48,72)$.
2. Find the prime factorizations:

• $48=2^4\times 3^1$
• $72=2^3\times 3^2$

1. Select the shared prime factors with the smallest exponents:

• Power of $2$: $2^3=8$
• Power of $3$: $3^1=3$

1. Multiply the minimum prime powers: $8\times 3=24$.
2. Calculate items per package:

• Pencils per package: $\frac{48}{24}=2$
• Notebooks per package: $\frac{72}{24}=3$

Answer: The clerk can make at most $24$ identical gift packages, with each package containing $2$ pencils and $3$ notebooks.

Check: $24\text{ packages}\times 2\text{ pencils}=48\text{ pencils}$, and $24\text{ packages}\times 3\text{ notebooks}=72\text{ notebooks}$. All items are used with zero remainder.

How to Check the Answer

Verify a calculated GCF using these two reliable mathematical checks:

Check 1: The Coprime Quotients Test

Divide each original number by the candidate GCF:

${\text{Quotient}}_1=\frac{a}{\text{GCF}},{\text{Quotient}}_2=\frac{b}{\text{GCF}}$

If $\text{GCF}({\text{Quotient}}_1,{\text{Quotient}}_2)=1$, then the quotients share no common factors, proving that the candidate GCF is the greatest possible common factor.

Check 2: The GCF-LCM Product Formula

For any two positive integers $a$ and $b$, the product of their GCF and LCM equals the product of the original numbers:

$\text{GCF}(a,b)\times \text{LCM}(a,b)=a\times b$

This fundamental identity links GCF and LCM directly. For example, for $12$ and $18$, $\text{GCF}=6$ and $\text{LCM}=36$. Checking: $6\times 36=216$, and $12\times 18=216$.

Common Mistakes