Find the greatest common factor (GCF/GCD) of two or more numbers
The greatest common factor (GCF), also called the greatest common divisor (GCD) or highest common factor (HCF), is the largest positive integer that divides two or more numbers without leaving a remainder. For example, the GCF of 12 and 18 is 6.
GCF is fundamental in simplifying fractions, solving problems involving ratios, and number theory. When you reduce a fraction like 12/18 to 2/3, you're dividing both numerator and denominator by their GCF (6).
There are several methods to find GCF: listing all factors, prime factorization, or the efficient Euclidean algorithm. The Euclidean algorithm, dating back over 2,300 years, remains the fastest method for large numbers.
List all factors of each number, find common ones, pick the largest.
Factor each number into primes, multiply common prime factors.
Repeatedly apply GCF(a,b) = GCF(b, a mod b) until remainder is 0.
Divide larger by smaller, use remainder to continue until zero.
Reference table for frequently needed GCF calculations:
| Numbers | GCF | Common Factors | LCM |
|---|---|---|---|
| 12, 18 | 6 | 1, 2, 3, 6 | 36 |
| 24, 36 | 12 | 1, 2, 3, 4, 6, 12 | 72 |
| 15, 25 | 5 | 1, 5 | 75 |
| 48, 60 | 12 | 1, 2, 3, 4, 6, 12 | 240 |
| 100, 75 | 25 | 1, 5, 25 | 300 |
| 8, 12, 20 | 4 | 1, 2, 4 | 120 |
Divide numerator and denominator by GCF to reduce to lowest terms. 24/36 → divide by GCF(24,36)=12 → 2/3.
Find largest square tile that evenly covers a floor. For a 12×18 ft room, use 6×6 ft tiles (GCF = 6).
Split items evenly. With 24 apples and 36 oranges, you can make GCF(24,36)=6 identical gift bags.
Simplify gear ratios using GCF. A 48:32 ratio simplifies to 3:2 (divide by GCF=16).
GCF is the largest number that divides all given numbers. LCM is the smallest number divisible by all given numbers. They're related: GCF × LCM = product of the two numbers.
Numbers with no common factors except 1 are called coprime or relatively prime. Their GCF is 1. Examples: 8 and 15, 9 and 14.
Find GCF of the first two numbers, then find GCF of that result with the third number, and so on. GCF(12, 18, 24) = GCF(GCF(12,18), 24) = GCF(6, 24) = 6.
No. GCF is always less than or equal to the smallest number. The GCF divides both numbers, so it can't exceed either of them.
Find the greatest common factor of 48 and 36 using the Euclidean algorithm, then verify with the LCM relationship.
ResultGCF(48, 36) = 12
Step 1: 48 mod 36 = 12, so GCF(48,36) = GCF(36,12). Step 2: 36 mod 12 = 0, so GCF(36,12) = 12. Verify: GCF × LCM = a × b → 12 × 144 = 1728 = 48 × 36.
GCF (greatest common factor) is the largest integer that divides every input number evenly, while LCM (least common multiple) is the smallest positive integer that every input divides into. They satisfy GCF(a,b) × LCM(a,b) = a × b for any two positive integers.
The Euclidean algorithm repeatedly replaces the pair (a, b) with (b, a mod b) until the remainder is zero. The last nonzero remainder is the GCF. It runs in O(log min(a,b)) steps, making it dramatically faster than listing factors for large numbers.
Factor each number into primes, then multiply the primes that appear in every factorization, using the lowest exponent each. Example: 48 = 2^4 × 3 and 36 = 2^2 × 3^2; shared primes are 2^2 and 3, giving GCF = 4 × 3 = 12.
Dividing the numerator and denominator by their GCF produces the fraction in lowest terms. For 36/48, GCF(36,48) = 12, so 36/48 = 3/4. Reducing once by the GCF is equivalent to repeatedly cancelling common factors.
Two integers are coprime when their GCF equals 1, meaning they share no prime factors. Examples include 8 and 15, or 14 and 25. Coprime pairs are important in cryptography, modular arithmetic, and fraction reduction.
GCF appears whenever you split quantities into equal groups, tile a region with the largest uniform square, simplify gear or aspect ratios, or align repeating cycles. It also underpins algorithms in cryptography (RSA key generation) and computer algebra systems.
It applies the associative property GCF(a, b, c) = GCF(GCF(a, b), c) and chains the Euclidean algorithm across the list, so any count of positive integers is supported with the same efficiency.
Found this calculator helpful? Share it with others:
