Common Factor Calculator (GCF/GCD)

Find the Greatest Common Factor of two or more numbers using prime factorization, the Euclidean algorithm, and list all common factors.

Enter Numbers

Enter two or more positive integers separated by commas

Result

Greatest Common Factor (GCF)
12
GCF of 48 and 36
All Common Factors 1, 2, 3, 4, 6, 12
Number of Common Factors 6

Step-by-Step Solution

GCF(48, 36) = 12

Understanding Common Factors and GCF

A common factor (also called a common divisor) of two or more numbers is a number that divides each of them without leaving a remainder. The Greatest Common Factor (GCF), also known as the Greatest Common Divisor (GCD) or Highest Common Factor (HCF), is the largest such number. For example, the GCF of 12 and 18 is 6 because 6 is the largest number that divides both 12 and 18 evenly.

Methods for Finding the GCF

Prime Factorization Method

Break each number into its prime factors, then multiply the common prime factors together.

GCF = product of shared primes

Euclidean Algorithm

Repeatedly divide the larger number by the smaller and take the remainder until it reaches zero.

GCF(a, b) = GCF(b, a mod b)

Listing Factors Method

List all factors of each number, then identify the common ones. The largest is the GCF.

GCF = max(common factors)

Division Method

Divide both numbers by common primes simultaneously until no common factor remains.

GCF = product of divisors

How the Euclidean Algorithm Works

The Euclidean algorithm is one of the oldest known algorithms, dating back to around 300 BC. It is based on the principle that the GCF of two numbers also divides their difference. The algorithm works by repeatedly replacing the larger number with the remainder of dividing the larger by the smaller, until one of the numbers becomes zero. The remaining non-zero number is the GCF.

For example, to find GCF(48, 36): 48 = 1 x 36 + 12, then 36 = 3 x 12 + 0, so GCF = 12. This method is extremely efficient even for very large numbers, making it the preferred algorithm in computer science.

How Prime Factorization Works

Prime factorization involves breaking a number down into its prime number components. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. To find the GCF using prime factorization, decompose each number into primes, identify the common prime factors, and multiply them together using the lowest exponent of each shared prime.

Properties of GCF

  • Commutative: GCF(a, b) = GCF(b, a) - the order does not matter.
  • Associative: GCF(a, GCF(b, c)) = GCF(GCF(a, b), c) - you can compute in any grouping.
  • Identity: GCF(a, 0) = a - any number's GCF with zero is itself.
  • Coprime numbers: If GCF(a, b) = 1, then a and b are called coprime or relatively prime.
  • Relationship with LCM: GCF(a, b) x LCM(a, b) = a x b.

Practical Applications

The GCF has many practical uses in everyday mathematics and beyond. It is essential for simplifying fractions to their lowest terms: divide both the numerator and denominator by their GCF. In construction and tiling, the GCF helps determine the largest tile size that evenly fits a rectangular area. In music theory, the GCF is used to find rhythmic patterns. In computer science, the Euclidean algorithm for GCF is fundamental to cryptographic systems like RSA encryption.

Tips for Finding Common Factors

  • Start by checking if the smaller number divides the larger number evenly - if so, the smaller number is the GCF.
  • For small numbers, listing all factors is often the quickest approach.
  • For large numbers, the Euclidean algorithm is the most efficient method.
  • Remember that 1 is always a common factor of any set of positive integers.
  • If all numbers are even, you can factor out 2 immediately to simplify.