GCF Calculator

Find the Greatest Common Factor (GCF), also called Greatest Common Divisor (GCD) or Highest Common Factor (HCF), of two or more numbers. View step-by-step solutions using prime factorization, the listing method, and the Euclidean algorithm.

Enter 2–10 positive integers. Separate with commas, spaces, or semicolons.

Greatest Common Factor (GCF)

12

of 48, 60

Least Common Multiple (LCM)

240

GCF × LCM = 2,880

Fraction Simplification

48/60 = 4/5 (÷ 12)

Method 1: Prime Factorization

48 = 2^4 × 3

60 = 2^2 × 3 × 5

Common primes (min power): 2^2 × 3

GCF = 2^2 × 3 = 12

Method 2: Listing Factors

Factors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48

Factors of 60: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60

Common: 1, 2, 3, 4, 6, 12

GCF = 12

Method 3: Euclidean Algorithm

60 = 1 × 48 + 12

48 = 4 × 12 + 0

GCF = 12

What Is the Greatest Common Factor (GCF)?

The Greatest Common Factor (GCF) of two or more integers is the largest positive integer that divides each of the given numbers without leaving a remainder. It is also known as the Greatest Common Divisor (GCD), Highest Common Factor (HCF), or Greatest Common Measure (GCM). For example, the factors of 12 are {1, 2, 3, 4, 6, 12} and the factors of 18 are {1, 2, 3, 6, 9, 18}. The largest factor they share is 6, so GCF(12, 18) = 6.

Three Methods to Find the GCF

Method 1: Prime Factorization

Express each number as a product of prime factors. The GCF is the product of all shared primes raised to the lowest power they appear in any of the numbers.

  • 48 = 2⁴ × 3
  • 60 = 2² × 3 × 5
  • Shared primes: 2 (min power 2) and 3 (min power 1)
  • GCF = 2² × 3 = 12

Method 2: Listing Factors

List all factors of each number and identify the largest one that appears in both lists:

  • Factors of 48: 1, 2, 3, 4, 6, 8, 12, 16, 24, 48
  • Factors of 60: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
  • Common: 1, 2, 3, 4, 6, 12
  • GCF = 12 (the largest common factor)

Method 3: Euclidean Algorithm

Repeatedly divide and take remainders until the remainder is 0. The last non-zero remainder is the GCF:

  • 60 = 1 × 48 + 12
  • 48 = 4 × 12 + 0
  • GCF = 12

The Euclidean Algorithm, described by Euclid in Elements (~300 BCE), is one of the oldest algorithms in mathematics and runs in O(log n) time — extremely efficient even for large numbers in the billions.

Understanding Your Results

The GCF tells you the largest “unit” that evenly divides all your numbers. Practical interpretation:

  • GCF = 1: The numbers are coprime (relatively prime) — they share no common factors.
  • GCF = one of the numbers: That number divides all the others evenly.
  • GCF > 1: All numbers can be divided by the GCF to produce simpler values.

Real-World Applications

  • Simplifying fractions: Divide numerator and denominator by their GCF. For 48/60: GCF(48,60) = 12, so 48/60 = 4/5.
  • Dividing objects into equal groups: You have 48 apples and 60 oranges. The largest number of identical gift baskets = GCF(48, 60) = 12 baskets, each with 4 apples and 5 oranges.
  • Tiling problems: You want to tile a 48×60 inch floor with square tiles. The largest square tile = GCF(48, 60) = 12 inches.
  • Cryptography: The RSA algorithm uses GCD computations to generate key pairs. The Euclidean Algorithm is central to computing modular inverses.

GCF × LCM Identity

For any two positive integers a and b:

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

This means: LCM(a, b) = (a × b) / GCF(a, b). Example: GCF(12, 18) = 6, so LCM(12, 18) = (12 × 18) / 6 = 36. This identity is frequently used in number theory and competitive mathematics.

Sources and References

  • Euclid (c. 300 BCE). Elements, Book VII, Propositions 1–2. Description of the Euclidean Algorithm.
  • Knuth, D.E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley. Analysis of GCD algorithms.
  • Common Core State Standards Initiative. CCSS.Math.Content.4.NF.A.1 — Fraction equivalence and simplification using factors.
  • Hardy, G.H. & Wright, E.M. (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press.

Frequently Asked Questions

What is the difference between GCF, GCD, and HCF?
GCF (Greatest Common Factor), GCD (Greatest Common Divisor), and HCF (Highest Common Factor) are three names for the same concept. GCF and GCD are used primarily in the United States, while HCF is more common in the UK, India, and Commonwealth countries. The mathematical definition is identical: the largest positive integer that divides each of the given numbers without a remainder. For example, GCF(12, 18) = GCD(12, 18) = HCF(12, 18) = 6.
How do I find the GCF of three or more numbers?
To find the GCF of three or more numbers, apply the GCF function pairwise: GCF(a, b, c) = GCF(GCF(a, b), c). For example, GCF(12, 18, 24): Step 1: GCF(12, 18) = 6. Step 2: GCF(6, 24) = 6. So GCF(12, 18, 24) = 6. This works because the GCF operation is both commutative and associative, meaning the order doesn't matter. This calculator handles up to 10 numbers at once using this iterative approach.
What is the relationship between GCF and LCM?
For any two positive integers a and b: GCF(a, b) × LCM(a, b) = a × b. This means you can find one if you know the other: LCM(a, b) = (a × b) / GCF(a, b). Example: For 12 and 18: GCF = 6, so LCM = (12 × 18) / 6 = 36. This identity is frequently used in competitive math (AMC, MATHCOUNTS) and is valid for all positive integer pairs. The relationship doesn't directly extend to three+ numbers without modification.
When is the GCF of two numbers equal to 1?
When GCF(a, b) = 1, the numbers are called 'coprime' or 'relatively prime.' This means they share no common factors other than 1. Examples: GCF(15, 28) = 1 (15 = 3×5, 28 = 4×7 — no shared primes). Consecutive integers are always coprime: GCF(n, n+1) = 1 for any n. Any prime number p is coprime with any number that is not a multiple of p. In fraction simplification, a fraction a/b is already in lowest terms when GCF(a, b) = 1.
How is the GCF used in simplifying fractions?
To simplify a fraction, divide both the numerator and denominator by their GCF. Example: Simplify 48/60. GCF(48, 60) = 12, so 48/60 = (48÷12)/(60÷12) = 4/5. This is the only reliable method for reducing fractions to their simplest form. It works because dividing both parts of a fraction by the same non-zero number produces an equivalent fraction. This is taught as early as 4th–5th grade in the US Common Core Standards (CCSS.Math.Content.4.NF.A.1).
What is the Euclidean Algorithm and why is it efficient?
The Euclidean Algorithm finds GCF(a, b) by repeatedly replacing the larger number with the remainder of dividing the two: GCF(a, b) = GCF(b, a mod b), repeating until the remainder is 0. The last non-zero remainder is the GCF. Example: GCF(252, 105) → GCF(105, 42) → GCF(42, 21) → GCF(21, 0) → GCF = 21. It runs in O(log(min(a,b))) time, making it extremely efficient even for very large numbers. Euclid described this algorithm in Book VII of Elements (~300 BCE), making it one of the oldest known algorithms still in use.

Related Tools