Greatest Common Factor Calculator
Calculate the greatest common factor (also called greatest common divisor) of two numbers. The GCF is the largest number that divides both numbers without a remainder.
The Greatest Common Factor (GCF), also called the Greatest Common Divisor (GCD), is the largest positive integer that divides two or more numbers without a remainder. For 48 and 36, the GCF is 12 — both numbers divide cleanly by 12 (48/12 = 4, 36/12 = 3), and no larger number divides both. The GCF is fundamental in number theory, fraction simplification, and many practical math problems.
The classic example: simplifying fractions. To reduce 48/36 to lowest terms, divide both by their GCF (12): 48/36 = 4/3. This works because the GCF is the largest factor common to both numerator and denominator. Any smaller common factor would also work but wouldn't fully simplify.
Several methods find the GCF: - **Prime factorization**: factor both, multiply common factors. Slow for large numbers. - **Euclidean algorithm**: repeatedly divide larger by smaller, take remainder. Fast and elegant. GCF(48, 36) = GCF(36, 12) = GCF(12, 0) = 12. - **Listing factors**: list all factors of each, find largest in common. Slow but intuitive.
The Euclidean algorithm (300 BC) is one of the oldest and most efficient algorithms still in use. Modern variants underlie RSA cryptography, computer algebra systems, and much of computational number theory.
GCF and LCM (Least Common Multiple) are deeply related: GCF(a,b) × LCM(a,b) = a × b. So if you know one, you can find the other.
Common applications: fraction simplification, ratio reduction, scheduling problems, packing/grouping problems, music theory (interval ratios), and any context involving common divisibility.
Inputs
Results
Greatest Common Factor (GCF)
12
Least Common Multiple (LCM)
144
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
Common Factors
1, 2, 3, 4, 6, 12
Formula
How to use this calculator
- Enter first positive integer.
- Enter second positive integer.
- Calculator returns GCF (greatest common factor / divisor).
- For more than 2 numbers: compute GCF pairwise.
- For fraction simplification: divide both by GCF.
- For LCM: LCM = (a × b) / GCF.
Worked examples
Simplifying a fraction
**Scenario:** Simplify 48/72. **Calculation:** GCF(48, 72). 48 = 2⁴ × 3, 72 = 2³ × 3². Common: 2³ × 3 = 24. So 48/72 = 48/24 / 72/24 = 2/3. **Result:** 48/72 = 2/3 in lowest terms. GCF gives the largest reducer; using smaller common factors would partially simplify but not fully.
Cutting equal boards
**Scenario:** Have 36-inch and 48-inch boards. Want equal-length pieces, no waste, as long as possible. **Calculation:** GCF(36, 48) = 12 inches. **Result:** Cut both into 12-inch pieces. 36 inch / 12 = 3 pieces from first; 48 inch / 12 = 4 pieces from second. Total: 7 equal pieces. Any larger piece size leaves waste; smaller is wasteful in different ways.
Reducing a ratio
**Scenario:** Ratio 60:84. Express in simplest form. **Calculation:** GCF(60, 84). 60 = 2²×3×5; 84 = 2²×3×7. Common: 2²×3 = 12. So 60:84 = 5:7. **Result:** 60:84 = 5:7. Coprime — can't be reduced further (GCF of 5 and 7 is 1). Used in scaling: if you have 5 cookies for 7 people, doubling = 10 for 14, etc.
When to use this calculator
**Use GCF for:**
- **Simplifying fractions**: reduce to lowest terms. - **Reducing ratios**: standardize proportions. - **Cutting/grouping problems**: largest equal pieces. - **Lowest common denominator**: LCD = (a × b)/GCF for fractions. - **Scheduling**: when periodic events align. - **Modular arithmetic**: cryptography, number theory. - **Music theory**: simplifying interval ratios. - **Diophantine equations**: existence of integer solutions.
**Best method per situation:**
- **Small numbers** (≤ 100): factor lists OK. - **Medium numbers** (100-10,000): prime factorization or Euclidean. - **Large numbers** (millions+): Euclidean algorithm dominant. - **Very large** (cryptographic, 100+ digits): binary GCD or specialized algorithms.
**Euclidean algorithm advantages:**
- Fast: O(log n) operations. - Simple: just division and modulo. - No need for prime factorization. - Works with any size integers. - Generalizable to polynomial GCDs.
**Common applications:**
- **Fraction simplification**: standard math operation. - **Reducing ratios**: 12:8 = 3:2. - **Tile/floor design**: largest tile fitting all dimensions. - **Container packing**: largest unit fitting in multiple sizes. - **Cryptography**: RSA key validation (GCF(e, φ(n)) = 1). - **Modular arithmetic**: solving linear congruences. - **Computer science**: hash table sizes, polynomial operations.
**GCF and LCM relationship:**
GCF × LCM = product of numbers.
For 12 and 18: GCF = 6, LCM = 36. 6 × 36 = 216 = 12 × 18. ✓
Use this to find one from the other.
**Common pitfalls:**
- **Confusing with LCM**: divisor vs multiple. - **Not fully simplifying**: small common factors don't fully reduce. - **GCF of negative numbers**: by convention, take positive. - **For non-integers**: not directly defined (need extension).
**Examples in nature/practical:**
- **Calendar synchronization**: lunar (29.5 days) vs solar (365 days) cycles. - **Music**: harmonic intervals as simple ratios. - **Gears**: rotation cycles align at LCM, GCF determines basic ratio. - **Architecture**: largest module fitting various dimensions. - **Manufacturing**: standard unit divisions.
**Software:**
- Excel: =GCD(A1, B1). - Python: math.gcd(48, 36) = 12. - Calculator: most scientific calculators have GCD button. - Programming: trivial loop or built-in.
**Algorithm variations:**
- **Standard Euclidean**: division-based. - **Binary Euclidean**: bit operations (no division, faster on some hardware). - **Extended Euclidean**: also finds Bezout coefficients. - **Lehmer's algorithm**: optimized for large numbers.
**Modern cryptography use:**
RSA key generation: 1. Pick large primes p, q. 2. Compute n = p × q. 3. Compute φ(n) = (p-1)(q-1). 4. Pick e such that GCF(e, φ(n)) = 1. 5. Find d (modular inverse of e mod φ(n)) using extended Euclidean.
GCF computation is critical and must be efficient for huge numbers (1024+ bits).
**Pitfalls:**
- **Confusing GCF and LCM**: distinct concepts. - **GCF(0, 0) = 0**: technically undefined or 0 by convention. - **For decimals**: convert to integers first (multiply by power of 10). - **For polynomials**: similar concept but polynomial GCF. - **Sign issues**: GCF usually positive.
Common mistakes to avoid
- Confusing GCF with LCM (largest divisor vs smallest multiple).
- Not simplifying fully (small common factors don't completely reduce).
- For three+ numbers: forgetting to apply pairwise (GCF(a,b,c) = GCF(GCF(a,b), c)).
- Using only listed common factors instead of "greatest".
- GCF of zero confusion (GCF(a, 0) = a).
- Computing for negative numbers without converting to positive.
- Trying to use prime factorization for very large numbers (slow).
- Not recognizing coprime numbers (GCF = 1).