Enter two or three whole numbers to find their Greatest Common Factor.
Greatest Common Factor Methods & Uses
The greatest common factor (GCF) is the largest whole number that divides every number in a set with no remainder. For 48 and 18 it is 6: 48 = 6 × 8 and 18 = 6 × 3, and no larger number divides both. Enter two or three numbers above to get the GCF with the Euclidean algorithm steps, each prime factorization and the LCM.
The Greatest Common Factor (GCF), also called Greatest Common Divisor (GCD) or Highest Common Factor (HCF), is the largest number that divides evenly into all given numbers with no remainder. GCF is essential for simplifying fractions and solving real-world division problems.
The Euclidean algorithm is the most efficient method: divide the larger number by the smaller, take the remainder, and repeat until the remainder is zero. The last non-zero remainder is the GCF.
Euclidean Algorithm
Prime Factorization Method
Simplifying Fractions with GCF
GCF vs LCM Relationship
GCF Reference Table
Common pairs from homework and fraction problems, with their prime factorizations and least common multiple.
| Numbers | Prime factors | GCF | LCM |
|---|---|---|---|
| 12 and 18 | 2² × 3 and 2 × 3² | 6 | 36 |
| 24 and 36 | 2³ × 3 and 2² × 3² | 12 | 72 |
| 15 and 25 | 3 × 5 and 5² | 5 | 75 |
| 16 and 40 | 2⁴ and 2³ × 5 | 8 | 80 |
| 27 and 45 | 3³ and 3² × 5 | 9 | 135 |
| 42 and 56 | 2 × 3 × 7 and 2³ × 7 | 14 | 168 |
| 48 and 180 | 2⁴ × 3 and 2² × 3² × 5 | 12 | 720 |
| 60 and 84 | 2² × 3 × 5 and 2² × 3 × 7 | 12 | 420 |
| 72 and 120 | 2³ × 3² and 2³ × 3 × 5 | 24 | 360 |
| 75 and 100 | 3 × 5² and 2² × 5² | 25 | 300 |
| 81 and 108 | 3⁴ and 2² × 3³ | 27 | 324 |
| 96 and 144 | 2⁵ × 3 and 2⁴ × 3² | 48 | 288 |
| 14 and 15 | 2 × 7 and 3 × 5 | 1 | 210 |
In each row the GCF takes the lowest power of every prime the numbers share, and the LCM takes the highest power of every prime that appears. When the GCF is 1, as with 14 and 15, the numbers are called coprime and the LCM is simply their product.
Worked Examples: Three Numbers and a Harder Pair
GCF(84, 126, 210)
By prime factors: 84 = 2² × 3 × 7, 126 = 2 × 3² × 7 and 210 = 2 × 3 × 5 × 7. The primes common to all three are 2, 3 and 7, each at its lowest power (1), so the GCF is 2 × 3 × 7 = 42. Chaining pairs gives the same result: GCF(84, 126) = 42, then GCF(42, 210) = 42.
GCF(1071, 462) with the Euclidean algorithm
Neither number factors easily by eye, which is where Euclid's method shines:
- 1071 = 2 × 462 + 147
- 462 = 3 × 147 + 21
- 147 = 7 × 21 + 0
The last non-zero remainder is 21. Three divisions settle it, and the number of steps grows only with the number of digits, which is why the calculator handles 18-digit numbers instantly.
Edge Cases and Common Mistakes
| Case | Result | Why |
|---|---|---|
| GCF(n, 1) | 1 | 1 has no other factors |
| GCF(n, n) | n | n divides itself |
| GCF(n, 2n) | n | the smaller number divides the larger |
| GCF(0, n) | n | every number divides 0 |
| GCF(0, 0) | 0 | no greatest divisor exists; 0 by convention |
| GCF(−12, 18) | 6 | signs are ignored, the GCF is positive |
| GCF(99, 100) | 1 | consecutive numbers are always coprime |
- Stopping at a common factor that is not the greatest. 2 divides both 24 and 36, but so do 4, 6 and 12. Dividing a fraction by 2 leaves 12/18, which still is not in lowest terms; dividing by 12 gives 2/3 in one step.
- Using the highest powers. Taking the highest power of each prime gives the LCM, not the GCF. For 12 and 18, the highest powers give 2² × 3² = 36 (the LCM); the lowest give 2 × 3 = 6 (the GCF).
- Including a prime that is not in every number. In GCF(84, 126, 210) the 5 appears only in 210, so it is left out.
- Applying it to decimals. The GCF is defined for whole numbers. For 1.2 and 1.8, scale by 10 to get 12 and 18, find the GCF (6), then scale back: 0.6.
The smallest shared multiple is on the LCM calculator, and the prime number calculator factors a single number. To reduce a fraction in one go, use the fraction calculator.
Method and sources. GCF by the Euclidean algorithm (Euclid, Elements, Book VII) and by prime factorization using the lowest shared powers; LCM from the highest powers, and GCF × LCM = a × b for two numbers. All table values and examples were computed in exact integer arithmetic. The calculator uses exact big-integer math, the Miller-Rabin test with fixed bases (deterministic for every number it accepts) and Pollard's rho method for factoring, so results are exact up to 10^18.
GCF Questions
What is the Greatest Common Factor (GCF)?
The GCF of two or more numbers is the largest number that divides evenly into all of them with no remainder. GCF(12, 18) = 6, because 6 divides both 12 and 18, and no number larger than 6 does. GCF is also called Greatest Common Divisor (GCD) or Highest Common Factor (HCF). These terms all refer to the same concept.
How do I find the GCF using the Euclidean algorithm?
Divide the larger number by the smaller and find the remainder. Replace the larger with the smaller, and the smaller with the remainder. Repeat until the remainder is 0. The last non-zero number is the GCF. Example GCF(56, 98): 98 = 1×56 + 42. Then GCF(56, 42): 56 = 1×42 + 14. Then GCF(42, 14): 42 = 3×14 + 0. GCF = 14. This algorithm is efficient even for very large numbers.
How do I find GCF using prime factorization?
Factor each number into its prime factors. Identify the primes that appear in all factorizations. Take the lowest power of each common prime. Multiply these together. Example: GCF(60, 90). 60 = 2² × 3 × 5. 90 = 2 × 3² × 5. Common primes: 2 (power 1), 3 (power 1), 5 (power 1). GCF = 2 × 3 × 5 = 30.
What is GCF used for in real life?
Simplifying fractions (divide numerator and denominator by GCF). Dividing into equal groups without leftovers: 24 apples and 36 oranges can be divided into GCF(24,36) = 12 equal groups, each with 2 apples and 3 oranges. Solving tile and grid problems: the largest square tile that fits a 12 ft by 18 ft room without cutting has side GCF(12,18) = 6 ft. Reducing ratios to simplest form.
What is the GCF of two prime numbers?
Always 1. Prime numbers have no factors other than 1 and themselves. Two different primes share no common factors, so GCF(7, 11) = 1, GCF(13, 17) = 1. Numbers whose GCF is 1 are called coprime or relatively prime. They do not need to be prime themselves: GCF(8, 9) = 1, even though neither 8 nor 9 is prime.
How do I find the GCF of three numbers?
Find GCF of the first two numbers, then find GCF of that result and the third number. Example: GCF(12, 18, 24). GCF(12, 18) = 6. GCF(6, 24) = 6. Answer: 6. This works because GCF is associative: GCF(a, b, c) = GCF(GCF(a, b), c). You can extend this to as many numbers as needed.
What is the difference between GCF and LCM?
GCF is the LARGEST number that divides all given numbers. LCM is the SMALLEST number that all given numbers divide into. GCF(4, 6) = 2, LCM(4, 6) = 12. They are related: GCF × LCM = product of the two numbers (for two numbers). GCF is used to simplify fractions; LCM is used to find common denominators for adding fractions. GCF ≤ min(a,b) and LCM ≥ max(a,b).
What is GCF(0, n) for any number n?
GCF(0, n) = n for any positive integer n. This is because every positive integer divides 0 (0 = n × 0), so the greatest divisor of both 0 and n is n itself. The Euclidean algorithm confirms this: GCF(0, n) divides until remainder = 0 immediately, leaving n as the GCF. GCF(0, 0) is typically defined as 0 by convention.
How do I use GCF to simplify a fraction?
Divide both the numerator and denominator by their GCF. Example: simplify 36/48. GCF(36, 48) = 12. 36/12 = 3, 48/12 = 4. Simplified fraction: 3/4. This works because dividing both parts of a fraction by the same number does not change its value. The result is in lowest terms when GCF(numerator, denominator) = 1.
Is GCF the same as GCD and HCF?
Yes, all three terms refer to the exact same mathematical concept. GCF (Greatest Common Factor) is most common in US elementary and middle school education. GCD (Greatest Common Divisor) is preferred in higher mathematics, computer science, and number theory. HCF (Highest Common Factor) is the standard term in UK, India, and many Commonwealth countries. They all mean: the largest positive integer that divides all given numbers without remainder.
Can the GCF of negative numbers be negative?
No. The GCF is defined as the greatest positive divisor, so signs are ignored: GCF(−12, 18) = GCF(12, 18) = 6. The calculator accepts negative entries and works with their absolute values.
What is the GCF of two consecutive numbers?
Always 1. Any number that divides both n and n + 1 must also divide their difference, which is 1. So GCF(99, 100) = 1 and GCF(1000, 1001) = 1, and consecutive numbers are always coprime.