Greatest Common Factor Calculator (GCF)

Math

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

Presets:

GCF(48, 72, 120) =

✓ Shares common factors

All Common Factors:

1234681224

Prime Factorization Method Steps

1. Prime Factorization of Each Number

48 = 2^4 × 3, 72 = 2^3 × 3^2, 120 = 2^3 × 3 × 5

Find the prime factors of all numbers.

2. Identify Common Prime Factors (Lowest Powers)

Common factors: 2^3 × 3

Select prime factors shared by all numbers, using their smallest exponents.

3. Multiply Common Primes

GCF = 2^3 × 3 = 24

The product of the common prime factors gives GCF: 24.

Euclidean Algorithm (Division Method for first 2 numbers)

Dividend (a)	Divisor (b)	Quotient (q)	Remainder (r)	Equation (a = b·q + r)
72	48	1	24	72 = 48 × 1 + 24
48	24	2	0	48 = 24 × 2 + 0

How This Calculator Works

The Greatest Common Factor (GCF), also called the Greatest Common Divisor (GCD) or Highest Common Factor (HCF), of two or more integers is the largest positive integer that divides each of the numbers with zero remainder. It is the primary tool for reducing fractions to lowest terms and factoring algebraic polynomials.

📐 The Euclidean Algorithm & Minimum Prime Power Formula

GCD(a, b) = GCD(b, a mod b) | GCD(a, b, c) = ∏ pᵢ^(min(eᵢ))

a, b: Positive integers whose greatest common divisor is being calculated

a mod b: Remainder when integer a is divided by integer b

pᵢ^(min(eᵢ)): Lowest power of each shared prime factor common to all numbers

Coprime: Condition where GCD(a, b) = 1 (no shared factors other than 1)

Key Mathematical Rules & Properties

Euclidean Algorithm Efficiency

Divide the larger number by the smaller number to get quotient q and remainder r. Replace (a, b) with (b, r) and repeat until remainder r = 0. The last non-zero divisor is the GCF.

Prime Factorization Method

Factor all numbers into primes. For every prime number shared by all inputs, take the lowest exponent among them and multiply.

Fraction Simplification

Dividing both numerator and denominator by their GCF guarantees the fraction is reduced to simplest form.

Multiple Numbers (Pairwise GCD)

For three or more numbers: GCD(a, b, c) = GCD(GCD(a, b), c).

✎

Worked Example: Finding GCF(48, 72, 120)

Determine the Greatest Common Factor of 48, 72, and 120.

Write prime factorizations for all three numbers:
48 = 2⁴ × 3¹
72 = 2³ × 3²
120 = 2³ × 3¹ × 5¹
Identify common prime factors: 2 and 3 (5 is not in 48 or 72).
Take lowest power of 2: min(4, 3, 3) = 2³ = 8.
Take lowest power of 3: min(1, 2, 1) = 3¹ = 3.
Multiply lowest powers: 2³ × 3¹ = 8 × 3 = 24.

Final Answer: GCF(48, 72, 120) = 24

Frequently Asked Questions

Can the GCF of two numbers ever be larger than either number?

No. The GCF must divide each number evenly, so it can never be larger than the smallest number in the input list (e.g. GCF(12, 24) = 12).

What does it mean if the GCF is 1?

When GCD(a, b) = 1, the numbers are termed "coprime" or "relatively prime". They share no integer divisors other than 1 (for example, 8 and 15 are coprime, even though neither is a prime number).

Why is the Euclidean algorithm faster than factoring for large numbers?

Factoring integers with hundreds of digits takes exponential time and is the basis of RSA encryption security. The Euclidean algorithm uses simple division with logarithmic time complexity O(log(min(a,b))).

What is the relationship between GCF and LCM?

For any two positive integers a and b: GCF(a, b) × LCM(a, b) = a × b.

Understanding your calculation

Method, example and limitations

How the calculation works

The greatest common factor is the largest positive integer that divides each input without a remainder. Repeated division through the Euclidean algorithm finds it efficiently.

Example to check

The greatest common factor of 18 and 24 is 6, which also reduces 18/24 to 3/4.

Before using the result

Use integers and check the treatment of zero and negative signs. GCF(0,0) does not have a largest positive common divisor.

Calculation methodology · Report a result that needs review