Greatest Common Factor (GCF) Calculator

Find the GCF using prime factorization with factor trees, common prime identification, and step-by-step computation. Supports 2-4 numbers.

Enter Numbers

Result

Greatest Common Factor
--

Step-by-Step Solution

GCF = product of common prime factors with lowest powers

Understanding 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 factor that two or more numbers share. It is determined by identifying the prime factorization of each number and taking the product of all common prime factors raised to their lowest powers.

Methods for Finding GCF

Prime Factorization

Break each number into prime factors. Multiply the common primes with lowest exponents.

48 = 2^4 x 3, 36 = 2^2 x 3^2 => GCF = 2^2 x 3 = 12

Factor Trees

A visual method for finding the prime factorization by repeatedly splitting composite numbers.

48 -> 2 x 24 -> 2 x 2 x 12 -> ...

Listing Factors

List all factors of each number and find the largest one they share.

Factors of 12: 1,2,3,4,6,12

Euclidean Algorithm

An efficient method using repeated division. GCF(a,b) = GCF(b, a mod b).

GCF(48,36) = GCF(36,12) = GCF(12,0) = 12

Step-by-Step Prime Factorization Method

  1. Find the prime factorization of each number (using a factor tree or division).
  2. Identify all prime factors that appear in every number's factorization.
  3. For each common prime factor, take the lowest power (exponent) that appears.
  4. Multiply these common prime factors together to get the GCF.

What is a Factor Tree?

A factor tree is a diagram used to break down a composite number into its prime factors. Start with the number at the top, then split it into two factors. Continue splitting composite factors until all branches end in prime numbers. The prime numbers at the ends of all branches are the complete prime factorization.

GCF vs LCM

The GCF and LCM (Least Common Multiple) are related but different concepts. The GCF is the largest shared factor, while the LCM is the smallest shared multiple. They are connected by the formula: GCF(a,b) x LCM(a,b) = a x b. If you know one, you can easily compute the other.

Applications of GCF

  • Simplifying fractions to their lowest terms
  • Factoring algebraic expressions (finding common factors)
  • Solving problems involving equal distribution or grouping
  • Tiling problems (finding the largest square tile for a rectangular floor)
  • Music theory (simplifying time signatures and rhythmic patterns)
  • Computer science (optimizing algorithms and data structures)

Worked Example

Find GCF(48, 36, 60):

  1. 48 = 24 x 3
  2. 36 = 22 x 32
  3. 60 = 22 x 3 x 5
  4. Common primes: 2 and 3
  5. Lowest power of 2: 22 = 4
  6. Lowest power of 3: 31 = 3
  7. GCF = 4 x 3 = 12