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.