GCF Calculator

Find the Greatest Common Factor (GCF), Greatest Common Divisor (GCD), or Highest Common Factor (HCF) of two or more numbers with step-by-step prime factorization and Euclidean division.

GCF & LCM Parameters

Live calculation

Enter 2 to 10 positive integers.

Quick Presets:

GCF and GCD refer to the same mathematical entity. When GCF equals 1, the numbers are coprime.

Greatest Common Factor (GCF)
12for [48, 60]
Least Common Multiple240
Product: 48 × 60GCF × LCM = 2,880
Simplified Fraction48 / 60 = 4 / 5
÷ 12

Method 1: Prime Factorization

48 = 2^4 × 3

60 = 2^2 × 3 × 5

Common Primes (lowest powers): 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

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

Largest Common Factor = 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 numbers without leaving a remainder. Also known as the Greatest Common Divisor (GCD) or Highest Common Factor (HCF), it is a foundational concept in number theory, algebraic factoring, and fraction arithmetic.

1. Fundamental GCF × LCM Product Identity
GCF(a, b) × LCM(a, b)=a × b⟹
a × bGCF(a, b)
=LCM(a, b)
2. Euclidean Division Algorithm Equation
a = q × b + r(where 0 ≤ r < b)⟹GCF(a, b) = GCF(b, r)
Step-by-Step Calculation Breakdown
Step 1: Prime Factorization (Example: 48 & 60)
• Prime factorization of 48 = 2⁴ × 3¹
• Prime factorization of 60 = 2² × 3¹ × 5¹
Step 2: Identify Minimum Power Shared Primes
• Common prime 2: min power = min(4, 2) = 2² = 4
• Common prime 3: min power = min(1, 1) = 3¹ = 3
• Prime 5 is not common to both numbers
Step 3: Multiply Common Prime Powers for Final GCF
• GCF(48, 60) = 2² × 3¹ = 4 × 3 = 12
• Fraction Simplification: 48/60 = (48 ÷ 12) / (60 ÷ 12) = 4/5

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 number.

Method 2: Listing Factors

List all factors of each number and identify the largest factor common to all sets.

Method 3: Euclidean Algorithm

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

Real-World Applications

  • Simplifying Fractions: Dividing both numerator and denominator by their GCF reduces fractions to lowest terms.
  • Even Group Distribution: Splitting unequal batches of items (e.g. 48 pens and 60 notebooks) into the largest identical gift packages.
  • Floor Tiling: Determining the largest square tile size required to tile a room without cutting tiles.
  • Cryptography: Key pair generation and modular arithmetic in the RSA encryption algorithm.

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 exact same concept. GCF and GCD are used primarily in the United States, while HCF is common in the UK, Canada, India, and Commonwealth nations. 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. Because the GCF operation is associative and commutative, order does not matter.
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 fundamental identity allows you to derive one if you know the other: LCM(a, b) = (a × b) / GCF(a, b). For example, for 12 and 18: GCF = 6, so LCM = (12 × 18) / 6 = 36.
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 (e.g., GCF(15, 28) = 1). Consecutive integers are always coprime: GCF(n, n+1) = 1 for any positive integer n.
How is the GCF used in simplifying fractions?
To reduce a fraction to its irreducible lowest terms, divide both the numerator and denominator by their GCF. For example, to simplify 48/60: GCF(48, 60) = 12, so (48 ÷ 12) / (60 ÷ 12) = 4/5.
What is the Euclidean Algorithm and why is it efficient?
The Euclidean Algorithm calculates GCF(a, b) by repeatedly replacing the larger number with the remainder of dividing the two: GCF(a, b) = GCF(b, a mod b), continuing until the remainder is 0. The last non-zero remainder is the GCF. It operates in logarithmic time O(log(min(a, b))), making it fast even for massive integers.

Related Tools