GCF Calculator
Find the greatest common factor (GCF/GCD) of two or more numbers.
Results
What Is the Greatest Common Factor?
The Greatest Common Factor (GCF), also called Greatest Common Divisor (GCD) or Highest Common Factor (HCF), is the largest positive integer that divides each of two or more numbers without leaving a remainder. GCF(48, 36) = 12, because 12 is the largest number that divides both 48 and 36 evenly.
Euclidean Algorithm
The most efficient method for finding GCF. Algorithm: GCF(a, b) = GCF(b, a mod b), repeating until the remainder is 0. Example: GCF(48, 36): 48 mod 36 = 12 → GCF(36, 12): 36 mod 12 = 0 → GCF = 12.
Prime Factorization Method
Factor both numbers into primes. The GCF is the product of all common prime factors, each taken to the lowest power. 48 = 2⁴ × 3, 36 = 2² × 3². Common factors: 2² and 3¹. GCF = 4 × 3 = 12.
Listing Factors Method
List all factors of each number and find the largest common one. Factors of 48: 1,2,3,4,6,8,12,16,24,48. Factors of 36: 1,2,3,4,6,9,12,18,36. Largest common: 12.
Applications
GCF is used to simplify fractions (divide numerator and denominator by their GCF), solve word problems about dividing items into equal groups, and in algebra to factor polynomials.
Worked Example: Word Problem
A baker has 48 chocolate cookies and 36 vanilla cookies. She wants to make identical gift bags with no cookies left over, using as many bags as possible. The maximum number of bags = GCF(48, 36). Using the Euclidean algorithm: GCF(48, 36) → 48 mod 36 = 12 → GCF(36, 12) → 36 mod 12 = 0 → GCF = 12. She can make 12 gift bags, each with 4 chocolate and 3 vanilla cookies.
GCF Reference Table
| Numbers | GCF | Method Used |
|---|---|---|
| 12 and 8 | 4 | Factors: {1,2,3,4,6,12} ∩ {1,2,4,8} |
| 100 and 75 | 25 | 100=2²×5², 75=3×5² → GCF=5²=25 |
| 17 and 13 | 1 | Both prime, coprime |
| 144 and 60 | 12 | Euclidean: 144 mod 60=24, 60 mod 24=12 |
| 1000 and 250 | 250 | 250 divides 1000 exactly |
Frequently Asked Questions
GCF(12,8): factors of 12 = {1,2,3,4,6,12}, factors of 8 = {1,2,4,8}. Largest common: 4. GCF = 4.
GCF is the largest number that divides both. LCM is the smallest number both divide into. GCF(a,b) × LCM(a,b) = a × b.
GCF(a, 0) = a for any positive integer a, since every number divides 0.
When two numbers have no common prime factors — they are called coprime or relatively prime. Example: GCF(8, 9) = 1.
Divide both numerator and denominator by their GCF. Example: 48/36 — GCF = 12 — simplifies to 4/3.
The Euclidean algorithm computes GCF(a,b) = GCF(b, a mod b) recursively until the remainder is 0. It's efficient because each step roughly halves the problem size, giving O(log n) time complexity. It works for numbers with hundreds of digits — far faster than factoring both numbers first.
Yes. GCF(a, b, c) = GCF(GCF(a, b), c). Apply the Euclidean algorithm repeatedly. For three or more numbers, compute GCF of the first pair, then take GCF of that result with the next number. For example: GCF(12, 18, 24) = GCF(GCF(12,18), 24) = GCF(6, 24) = 6.