DigitalCalculators.net

Menu

Greatest Common Factor (GCF) Calculator

Steps & Prime Factorization

🔹 What Is the Greatest Common Factor?

The Greatest Common Factor (GCF), also known as the Greatest Common Divisor (GCD) or Highest Common Factor (HCF), is the largest positive integer that divides two or more numbers without leaving a remainder.

For example, the GCF of 84 and 126 is 42, because both numbers are divisible by 42, and no larger number divides them both evenly.

The GCF is widely used in simplifying fractions, reducing ratios, and dividing objects into equal groups. It is also a fundamental concept in number theory and is often paired with the Least Common Multiple (LCM) in problem solving.

🔹 Methods to Find the GCF

There are several ways to calculate the Greatest Common Factor (GCF). The most common methods are:

  • Euclidean Algorithm – a step-by-step division process that finds the GCF efficiently, even for very large numbers.
  • Prime Factorization – breaking numbers down into their prime factors and identifying the common factors.
  • Listing Factors – writing out all factors of each number and choosing the largest one they share (best for small numbers).

Among these, the Euclidean Algorithm is the fastest for larger numbers, while Prime Factorization is often preferred when learning the basics of factors and multiples.

🔹 Finding the GCF Using the Euclidean Algorithm

The Euclidean Algorithm is one of the most efficient ways to find the Greatest Common Factor (GCF). It works by repeatedly dividing the larger number by the smaller number until the remainder is zero. The last non-zero divisor is the GCF.

Steps:

  • Divide the larger number by the smaller number.
  • Take the remainder as the new divisor.
  • Repeat the process until the remainder becomes zero.
  • The last non-zero remainder is the GCF.

Example: Find the GCF of 252 and 105.

StepCalculation
1252 ÷ 105 = 2 remainder 42
2105 ÷ 42 = 2 remainder 21
342 ÷ 21 = 2 remainder 0

he last non-zero divisor is 21, so GCF(252, 105) = 21.

🔹 Finding the GCF Using Prime Factorization

The Prime Factorization Method breaks numbers down into their prime factors and then identifies the common prime factors. Multiplying these common factors together gives the GCF.

Steps:

  • Write each number as a product of its prime factors.
  • Identify the prime factors that both numbers share.
  • Multiply the shared factors to get the GCF.

Example: Find the GCF of 60 and 48.

NumberPrime Factorization
602 × 2 × 3 × 5 = 2² × 3 × 5
482 × 2 × 2 × 2 × 3 = 2⁴ × 3

Common prime factors: 2² × 3 = 12
herefore, GCF(60, 48) = 12.

🔹 Finding the GCF by Listing Factors

The Listing Factors Method is the simplest way to find the GCF, especially for small numbers. It involves writing down all the factors of each number and identifying the largest one they share.

Steps:

  • List all factors of the first number.
  • List all factors of the second number.
  • Identify the largest factor that appears in both lists.

Example: Find the GCF of 18 and 24.

NumberFactors
181, 2, 3, 6, 9, 18
241, 2, 3, 4, 6, 8, 12, 24

The common factors are 1, 2, 3, and 6. The largest of these is 6, so GCF(18, 24) = 6.

🔹 Worked Examples of GCF

Below are some step-by-step examples showing how to calculate the Greatest Common Factor (GCF) using different methods.

Example 1: GCF of 48 and 60 (Prime Factorization)

NumberPrime Factorization
482 × 2 × 2 × 2 × 3 = 2⁴ × 3
602 × 2 × 3 × 5 = 2² × 3 × 5

Common prime factors = 2² × 3 = 12 Therefore, GCF(48, 60) = 12.

Example 2: GCF of 252 and 105 (Euclidean Algorithm)

StepCalculation
1252 ÷ 105 = 2 remainder 42
2105 ÷ 42 = 2 remainder 21
342 ÷ 21 = 2 remainder 0

The last non-zero remainder is 21. herefore, GCF(252, 105) = 21.

Example 3: GCF of 36, 60, and 84 (More Than Two Numbers)

Step 1: GCF(36, 60) = 12 Step 2: GCF(12, 84) = 12 herefore, GCF(36, 60, 84) = 12.

🔹 Difference Between GCF and LCM

The Greatest Common Factor (GCF) and the Least Common Multiple (LCM) are two related but different concepts in mathematics.

Feature GCF (Greatest Common Factor) LCM (Least Common Multiple)
Definition Largest integer that divides two or more numbers without a remainder. Smallest integer that is divisible by two or more numbers.
Purpose Used to simplify fractions, reduce ratios, and divide items into equal groups. Used to find common denominators and schedule events in repeating cycles.
Formula For two numbers a and b:
a × b = GCF(a, b) × LCM(a, b)
Example GCF(12, 18) = 6 LCM(12, 18) = 36

In short: the GCF looks for the largest common divisor, while the LCM looks for the smallest common multiple. You can try our LCM Calculator for practice with multiples.

🔹 Applications of GCF in Real Life

The Greatest Common Factor (GCF) appears in many everyday tasks where you need to split, reduce, or standardize quantities. Here are common use cases and how GCF helps.

Situation How GCF Helps Quick Example
Simplifying fractions Divide numerator and denominator by the GCF to reduce to lowest terms. 60/84 → GCF = 12 → 5/7 (try our Fraction Calculator)
Reducing ratios Divide both parts of a ratio by the GCF for a minimal ratio. 42:56 → GCF = 14 → 3:4
Fair distribution / batching Find the largest equal group size that uses all items without leftovers. 96 red and 72 blue tiles → GCF = 24 → 24 equal sets
Packaging & cutting Choose the largest identical piece size that fits evenly into all lengths. Cables of 120 cm and 84 cm → GCF = 12 cm segments
Scheduling with cycles When cycles must align on a shared interval, GCF gives the largest joint step. Rest days every 9 and 12 days → joint step = GCF(9,12)=3 days
Percent & scaling problems Normalize numbers before computing percentages or scaled models. Reduce 150:180 by GCF 30 → 5:6 (use Percentage Calculator)

In general, whenever you want to standardize units, avoid leftovers, or simplify proportions, start by finding the GCF. For multiples-focused tasks, see the LCM Calculator.

🔹 Relation Between GCF and LCM

For any two non-zero integers a and b, the Greatest Common Factor (GCF) and the Least Common Multiple (LCM) are linked by the identity:

Identity a × b = GCF(a, b) × LCM(a, b)

Why it works: GCF contains the shared prime factors (with the smallest exponents), while LCM contains every prime factor present in either number (with the largest exponents). Multiplying them reconstructs the full product a × b.

Example: Let a = 12 and b = 18. GCF(12, 18) = 6, LCM(12, 18) = 36. a × b = 12 × 18 = 216 and GCF × LCM = 6 × 36 = 216. The identity holds.

Note for more than two numbers: the simple identity above is strictly for pairs. For three or more integers, compute GCF or LCM iteratively (e.g., LCM(a, b, c) = LCM(LCM(a, b), c)) and pair the formula as needed.

Need to compute multiples? Try the LCM Calculator.

🔹 GCF Practice Problems (with Answers)

Try these problems to reinforce how to find the Greatest Common Factor (GCF). Use any method: Euclidean Algorithm, Prime Factorization, or factor listing. For help with reducing fractions after you find the GCF, see our Fraction Calculator.

Beginner

  1. Find GCF(18, 24)
    Show answerGCF(18, 24) = 6
  2. Find GCF(30, 45)
    Show answerGCF(30, 45) = 15
  3. Simplify the fraction 56/84 using GCF
    Show answerGCF = 28 → 56/84 = 2/3

Intermediate

  1. Find GCF(72, 108)
    Show answerGCF(72, 108) = 36
  2. Find GCF(84, 126)
    Show answerGCF(84, 126) = 42
  3. Find GCF(36, 60, 84)
    Show answerGCF(36, 60) = 12; GCF(12, 84) = 12

Advanced

  1. Find GCF(252, 105) using the Euclidean Algorithm
    Show answer252 = 105×2 + 42; 105 = 42×2 + 21; 42 = 21×2 + 0 → GCF = 21
  2. Use prime factorization to find GCF(360, 168)
    Show answer 360 = 23 × 32 × 5; 168 = 23 × 3 × 7 → GCF = 23 × 3 = 24
  3. Find GCF(420, 588, 924)
    Show answer GCF(420, 588) = 84; GCF(84, 924) = 84

When you need multiples instead of factors, switch to the LCM Calculator.

🔹 Frequently Asked Questions (GCF)

▼What is the Greatest Common Factor (GCF)? Is it the same as GCD or HCF?
Yes—GCF, GCD (Greatest Common Divisor), and HCF (Highest Common Factor) are the same concept: the largest integer that divides two or more integers without a remainder.
▼What is the quickest way to find the GCF?
For large numbers, the Euclidean Algorithm is fastest. For teaching or small numbers, prime factorization or listing factors can be clearer.
▼Can I find the GCF of three or more numbers?
Yes. Compute GCF pairwise: GCF(a, b, c) = GCF(GCF(a, b), c). You can extend the process to any count of integers.
▼What if one number is 0? What if numbers are negative?
By convention, GCF(0, n) = |n| for non-zero n. If both numbers are 0, the GCF is undefined. For negative numbers, GCF is always taken using absolute values, so signs do not affect the result.
▼What is the GCF of two prime numbers?
If they are different primes, their only common divisor is 1, so the GCF is 1. If the primes are equal (e.g., 13 and 13), the GCF is that prime (13).
▼How is GCF related to LCM?
For non-zero integers a and b: a × b = GCF(a, b) × LCM(a, b). Knowing one lets you compute the other from the product a×b.
▼What does it mean if the GCF is 1?
The numbers are coprime (relatively prime). They share no prime factors, and their simplest ratio already uses the smallest integers.
▼Can I compute GCF for decimals or fractions?
Convert decimals to integers by removing decimal places (e.g., multiply both numbers by 10, 100, etc.). For fractions, use integer numerators and denominators. Our calculator expects integers.
▼When should I use GCF vs LCM?
Use GCF to reduce or split (simplifying fractions, reducing ratios, equal grouping). Use LCM to combine or align (finding common denominators, synchronizing cycles).
▼Why do some methods show different steps but the same GCF?
Methods differ in process but are mathematically equivalent. Whether you use Euclid’s division, prime factorization, or factor lists, you’ll reach the same greatest common factor.

🔹 References & Sources

The following resources were used to compile definitions, formulas, and examples for the Greatest Common Factor (GCF):

Source Type Link
Khan Academy – Greatest Common Factor Educational Website Visit
Paul’s Online Math Notes – GCF & LCM Educational Website Visit
Math is Fun – Factors and Multiples Educational Website Visit
Elementary Number Theory (David M. Burton) Textbook Book
Wikipedia – Greatest Common Divisor Reference Article Visit