CALTRX

Greatest Common Factor Calculator

Find the greatest common factor of two or more numbers using prime factorization. Shows all factors and step-by-step working. Essential for simplifying fractions.

Enter your values above to see the results.

Tips & Notes

  • ✓GCF(a, a) = a and GCF(a, 1) = 1 always. If numbers share no prime factors, GCF = 1 (coprime).
  • ✓For three numbers: GCF(a,b,c) = GCF(GCF(a,b), c). Apply pairwise then combine.
  • ✓If the smaller number divides the larger evenly, GCF = smaller. GCF(6,18) = 6 since 18÷6=3.
  • ✓Use GCF to simplify fractions in one step: 72/96 → GCF=24 → 3/4 directly.
  • ✓Find LCM quickly from GCF: LCM(a,b) = (a×b)/GCF(a,b). LCM(12,18) = 216/6 = 36.

Common Mistakes

  • ✗Confusing GCF with LCM. GCF(4,6)=2 (largest common divisor). LCM(4,6)=12 (smallest common multiple).
  • ✗Taking minimum exponents of non-shared primes. GCF uses minimum exponents of SHARED primes only.
  • ✗Stopping Euclidean algorithm too early. GCF(48,18): first step gives 12, but GCF is not 12 yet — continue.
  • ✗Using subtraction instead of mod in Euclidean algorithm — use remainder after division, not subtraction.
  • ✗For three numbers, applying GCF to only two then stopping — must include all numbers.

Greatest Common Factor Calculator Overview

The Greatest Common Factor (GCF) — also called the Greatest Common Divisor (GCD) — is the largest positive integer that divides evenly into two or more numbers with no remainder. The GCF reveals the deepest common divisibility shared by numbers, serving as the foundation for simplifying fractions, reducing ratios, solving tiling and packing problems, and generating the LCM. Every common factor of two numbers divides their GCF, making GCF the master key to the entire set of common divisors.

Euclidean Algorithm — the fastest method for any size numbers:

GCF(a, b) = GCF(b, a mod b) — repeat until remainder = 0, final nonzero remainder is the GCF
EX: GCF(48, 18) → 48 mod 18=12 → GCF(18,12) → 18 mod 12=6 → GCF(12,6) → 12 mod 6=0 → GCF = 6
EX: GCF(252, 105) → 252 mod 105=42 → GCF(105,42) → 105 mod 42=21 → GCF(42,21) → 42 mod 21=0 → GCF=21
Prime Factorization method — take minimum power of each shared prime:
EX: GCF(48,36) → 48=2⁴×3, 36=2²×3² → shared primes: 2 (min power 2), 3 (min power 1) → GCF=2²×3=12
Fraction simplification using GCF:
EX: 84/126 → GCF(84,126)=42 → 84÷42=2, 126÷42=3 → simplified: 2/3 in one step
GCF and LCM relationship: GCF(a,b) × LCM(a,b) = a × b always. Use this to find LCM in one step once GCF is known:
EX: GCF(12,18)=6, so LCM=12×18/6=36 | verify: GCF(12,18)×LCM(12,18) = 6×36 = 216 = 12×18 ✓
The GCF satisfies two useful identities: GCF(a, 1) = 1 for any a, and GCF(a, a) = a. If GCF(a, b) = 1, the numbers are coprime — they share no common factor, which means their LCM equals their product. Coprime pairs appear frequently in fraction arithmetic: when a numerator and denominator are coprime, the fraction is already in its simplest form without any reduction needed. The Euclidean algorithm, developed around 300 BCE, remains one of the most efficient algorithms ever devised — its worst-case performance grows only logarithmically with input size. The GCF has a geometric interpretation that makes tiling problems immediate: the largest square tile that fits exactly into a p × q rectangle without any cuts is a square with side length GCF(p, q).

Frequently Asked Questions

The GCF (Greatest Common Factor) is the largest integer that divides all given numbers with no remainder. Method 1 — prime factorization: factor each number, identify shared primes, take the minimum exponent of each. GCF(12, 18): 12 = 2²×3, 18 = 2×3². Shared: 2^min(2,1) × 3^min(1,2) = 2¹×3¹ = 6. Method 2 — Euclidean algorithm: GCF(18, 12) = GCF(12, 6) = GCF(6, 0) = 6. The Euclidean algorithm is faster for large numbers.

The Euclidean algorithm uses repeated division: GCF(a, b) = GCF(b, a mod b), stopping when remainder = 0. Example: GCF(252, 105). 252 = 2×105 + 42. GCF(252,105) = GCF(105,42). 105 = 2×42 + 21. GCF(105,42) = GCF(42,21). 42 = 2×21 + 0. GCF(42,21) = 21. So GCF(252,105) = 21. Verify: 252/21 = 12 ✓, 105/21 = 5 ✓. This algorithm works in at most 2×(number of digits) steps.

GCF is used to simplify fractions to lowest terms: divide numerator and denominator by their GCF. 36/48: GCF(36,48) = 12. 36÷12 = 3, 48÷12 = 4 → simplified to 3/4. Verify: GCF(3,4) = 1 ✓ (fully reduced). GCF also appears in cutting problems — tiling a 12 × 18 room with square tiles of maximum size uses GCF(12,18) = 6, so 6×6 tiles. Distributing 36 apples and 48 oranges into equal groups uses GCF(36,48) = 12 groups of 3 apples and 4 oranges.

GCF(LCM(a,b)) × GCF(a,b) = a × b for any two positive integers. Example: a=12, b=18. GCF = 6, LCM = 36. 6 × 36 = 216 = 12 × 18 ✓. This relationship lets you find LCM quickly once you have GCF: LCM(a,b) = a × b / GCF(a,b). Example: LCM(12,18) = 12×18/6 = 216/6 = 36. The formula extends to fractions: adding 1/12 + 1/18 requires LCM(12,18) = 36 as the common denominator.

If GCF(a, b) = 1, the numbers are called coprime or relatively prime — they share no common factors other than 1. Example: GCF(8, 15) = 1 (8 = 2³, 15 = 3×5 — no shared prime factors). Coprime numbers are important in cryptography: RSA encryption requires two large coprime numbers. In fractions, a/b is in lowest terms if and only if GCF(a, b) = 1. Consecutive integers are always coprime: GCF(n, n+1) = 1 for all positive integers n.

For three or more numbers, compute GCF iteratively: GCF(a, b, c) = GCF(GCF(a, b), c). Example: GCF(24, 36, 48). GCF(24, 36) = 12. GCF(12, 48) = 12. So GCF(24, 36, 48) = 12. Verify: 24÷12=2 ✓, 36÷12=3 ✓, 48÷12=4 ✓. For many numbers, keep applying GCF pairwise — order does not matter. The result equals the product of all prime factors that appear in every single number, each taken to its minimum exponent.