Greatest Common Factor Calculator

Find the largest integer that divides two or more numbers without leaving a remainder. Perfect for simplifying fractions and solving math problems.

Calculate GCF

Enter two positive integers:

What is the Greatest Common Factor?

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

Example: GCF of 12 and 18

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

Factors of 18: 1, 2, 3, 6, 9, 18

Common factors: 1, 2, 3, 6

Greatest Common Factor: 6

The Euclidean Algorithm

This calculator uses the Euclidean algorithm, which is an efficient method for computing the GCF:

GCF(a, b) = GCF(b, a mod b)
Repeat until b = 0, then GCF = a

Example Using Euclidean Algorithm

Find GCF(48, 18):

GCF(48, 18) = GCF(18, 48 ÷ 18 = 30)
Wait, that's not right. Let me fix this:
GCF(48, 18) = GCF(18, 48 mod 18 = 12)
GCF(18, 12) = GCF(12, 18 mod 12 = 6)
GCF(12, 6) = GCF(6, 12 mod 6 = 0)
When remainder is 0, GCF = 6

Applications of GCF

📚 Fraction Simplification

Reduce fractions to lowest terms by dividing numerator and denominator by GCF

🔢 LCM Calculation

Use GCF to find Least Common Multiple: LCM(a,b) = (a × b) ÷ GCF(a,b)

📐 Ratio Simplification

Simplify ratios by dividing all terms by their GCF

🏗️ Engineering

Calculate gear ratios and mechanical advantage

Special Cases

  • Coprime Numbers: GCF = 1 (like 8 and 15)
  • Identical Numbers: GCF = the number itself
  • One is Multiple: GCF(12, 6) = 6
  • Prime Numbers: GCF of distinct primes = 1

Fraction Simplification Examples

Original Fraction GCF of Numerator/Denominator Simplified Fraction
12/18 GCF(12,18) = 6 2/3
15/20 GCF(15,20) = 5 3/4
24/36 GCF(24,36) = 12 2/3
16/24 GCF(16,24) = 8 2/3

GCF Properties

  • GCF(a, b) = GCF(b, a) - Commutative property
  • GCF(a, b) = GCF(-a, b) = GCF(a, -b) - Absolute values
  • If d divides both a and b, then d ≤ GCF(a, b)
  • GCF(a, b) × LCM(a, b) = a × b

Algorithm Efficiency

The Euclidean algorithm is very efficient:

  • Time complexity: O(log min(a,b))
  • Works well even for very large numbers
  • Ancient algorithm (over 2,300 years old)
  • Used in many computer science applications

💡 Tip: The GCF is always a positive integer. If you get a negative result, check your input - the algorithm should handle negative numbers by taking absolute values.

Real-World Examples

  • 🎂 Baking: Recipe scaling using fraction simplification
  • ⚙️ Engineering: Gear ratio calculations
  • 🖼️ Photography: Aspect ratio simplification
  • 📏 Carpentry: Measurement and cutting calculations
  • 🎵 Music: Rhythm and time signature simplification