What is the Greatest Common Factor?
The Greatest Common Factor (GCF) — also known as the Greatest Common Divisor (GCD), Highest Common Factor (HCF), or Highest Common Divisor (HCD) — is the largest positive integer that divides each of the given numbers without a remainder. For example, the GCF of 72 and 40 is 8, because 8 is the largest number that divides both 72 and 40 evenly.
Understanding the GCF is essential in mathematics for simplifying fractions, factoring polynomials, solving word problems involving equal groups, and much more.
How to Find the Greatest Common Factor
There are several methods to calculate the GCF. Our calculator shows results using the most popular approaches:
- List of factors — list all factors of each number and find the largest common one
- Prime factorization — break each number into prime factors and multiply the shared ones
- Euclidean algorithm — use repeated division (modulo) to find the GCF efficiently
GCF Finder — List of Factors Method
The simplest method: list all positive divisors of each number, then find the largest number that appears in every list.
Example: Find GCF(72, 40)
- Factors of 72: 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72
- Factors of 40: 1, 2, 4, 5, 8, 10, 20, 40
- Common factors: 1, 2, 4, 8
- GCF = 8
This method is easy to understand but becomes time-consuming for large numbers — which is exactly why our GCF calculator is so useful!
Prime Factorization Method
Express each number as a product of prime numbers. The GCF is the product of all shared prime factors, using the lowest power that appears in each factorization.
Example: Find GCF(72, 40)
- 72 = 2³ × 3²
- 40 = 2³ × 5
- Shared prime factors: 2³
- GCF = 2³ = 8
Larger example: Find GCF(33,264 and 35,640)
- 33,264 = 2⁴ × 3³ × 7 × 11
- 35,640 = 2³ × 3⁴ × 5 × 11
- Common: 2³ × 3³ × 11 = 8 × 27 × 11 = 2,376
Euclidean Algorithm
The Euclidean algorithm is one of the oldest and most efficient methods for computing the GCF. It is based on the principle that GCF(a, b) = GCF(b, a mod b). We apply this repeatedly until the remainder is 0.
Example: Find GCF(72, 40)
- 72 mod 40 = 32 → GCF(40, 32)
- 40 mod 32 = 8 → GCF(32, 8)
- 32 mod 8 = 0 → GCF = 8
The modulo-based version of the Euclidean algorithm is far more efficient than simple subtraction for large numbers. For instance, GCF(35,640 and 33,264) is found in just two steps using modulo.
Binary GCD Algorithm (Stein's Algorithm)
The binary GCD algorithm uses only subtraction and bitwise operations (shifting), making it highly efficient on binary computers. It works by repeatedly halving even numbers and subtracting odd ones until two equal values remain. While not shown step-by-step in the calculator, it always produces the same result as the Euclidean method.
Coprime Numbers
Two numbers are called coprime (or relatively prime) if their GCF equals 1. Coprime numbers share no common factor other than 1. For example, 8 and 15 are coprime (GCF = 1), while 8 and 12 are not (GCF = 4).
Coprimality is important in number theory, cryptography, and when simplifying fractions to their lowest terms.
GCF of More Than Two Numbers
To find the greatest common factor of three or more numbers, compute the GCF of the first two, then take the GCF of that result with the third number, and so on.
Example: GCF(12, 18, 24)
- GCF(12, 18) = 6
- GCF(6, 24) = 6
- GCF(12, 18, 24) = 6
Our calculator supports up to 15 numbers at once.
Least Common Multiple and GCF
The GCF and the Least Common Multiple (LCM) are closely related. For any two positive integers a and b:
GCF(a, b) × LCM(a, b) = a × b
This means you can calculate the LCM once you know the GCF: LCM(a, b) = (a × b) / GCF(a, b). Our calculator displays both the GCF and LCM simultaneously.
Properties of GCF
- Commutative: GCF(a, b) = GCF(b, a)
- Associative: GCF(a, GCF(b, c)) = GCF(GCF(a, b), c)
- Identity: GCF(a, 0) = a
- Idempotent: GCF(a, a) = a
- GCF(a, b) always divides both a and b
- GCF(a, b) ≤ min(a, b)
- If a divides b, then GCF(a, b) = a
Frequently Asked Questions
What is the GCF of 0 and any number?
GCF(a, 0) = a. Zero is divisible by every positive integer, so the GCF of 0 and a is simply a.
Can the GCF be larger than any of the numbers?
No. The GCF is always less than or equal to the smallest number in the set, since it must divide all numbers.
How is GCF used to simplify fractions?
To reduce a fraction a/b to its simplest form, divide both numerator and denominator by GCF(a, b). For example, 72/40 → divide by GCF(72,40)=8 → 9/5.
What is the difference between GCF and LCM?
The GCF is the largest factor shared by a set of numbers. The LCM is the smallest multiple that all numbers share. They serve opposite but complementary purposes.