GCF Calculator – Greatest Common Factor

What Is the Greatest Common Factor (GCF)?

The Greatest Common Factor (GCF) — also called the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) — is the largest positive integer that divides two or more numbers without leaving a remainder. It is a fundamental concept in number theory and has practical applications in simplifying fractions, solving word problems, and distributing items into equal groups.

For example, the factors of 24 are: 1, 2, 3, 4, 6, 8, 12, 24. The factors of 36 are: 1, 2, 3, 4, 6, 9, 12, 18, 36. The common factors are: 1, 2, 3, 4, 6, 12. The greatest of these is 12, so GCF(24, 36) = 12.

The GCF is related to the Least Common Multiple (LCM) through the fundamental identity: GCF(a, b) × LCM(a, b) = a × b. This means once you know the GCF, you can calculate the LCM quickly, and vice versa. For 24 and 36: GCF = 12, LCM = 24×36/12 = 72.

Methods to Find the GCF

There are three main methods for finding the GCF. Each has its advantages depending on the size of the numbers involved.

Method 1: Listing Factors

List all factors of each number, then identify the largest common one. This works well for small numbers but becomes tedious for large ones.

Example: GCF(18, 24). Factors of 18: 1, 2, 3, 6, 9, 18. Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24. Common: 1, 2, 3, 6. GCF = 6.

Method 2: Prime Factorization

Express each number as a product of prime factors, then multiply the common prime factors (using the lowest exponent for each).

Example: GCF(120, 180). 120 = 2³ × 3 × 5. 180 = 2² × 3² × 5. Common prime factors: 2² × 3 × 5 = 4 × 3 × 5 = 60. GCF(120, 180) = 60.

Method 3: Euclidean Algorithm

The Euclidean algorithm is the most efficient method, especially for large numbers. It's based on the property that GCF(a, b) = GCF(b, a mod b). Repeat until the remainder is 0; the last non-zero remainder is the GCF.

Example: GCF(252, 105). Step 1: 252 = 2 × 105 + 42. Step 2: 105 = 2 × 42 + 21. Step 3: 42 = 2 × 21 + 0. GCF = 21.

GCF Reference Table: Common Number Pairs

Here are GCF values for frequently used number pairs in math problems and fraction simplification:

Notice that when GCF(a, b) = b, b divides a evenly. When GCF(a, b) = 1, the numbers are coprime — they share no common factors other than 1. Coprime numbers are important in cryptography, particularly in RSA encryption where choosing coprime numbers is essential for key generation.

Simplifying Fractions Using GCF

The most common everyday use of GCF is simplifying fractions to lowest terms. To simplify a fraction a/b, divide both numerator and denominator by GCF(a, b).

Examples:

• 48/60: GCF(48, 60) = 12. → 48÷12 / 60÷12 = 4/5 ✓
• 56/84: GCF(56, 84) = 28. → 56÷28 / 84÷28 = 2/3 ✓
• 75/100: GCF(75, 100) = 25. → 75÷25 / 100÷25 = 3/4 ✓
• 144/360: GCF(144, 360) = 72. → 144÷72 / 360÷72 = 2/5 ✓

A fraction is in lowest terms (simplest form) when GCF(numerator, denominator) = 1. For example, 3/5 is already in lowest terms because GCF(3, 5) = 1. The fraction 6/10 is not in lowest terms because GCF(6, 10) = 2 → 3/5.

In cooking, GCF helps scale recipes. If a recipe serves 24 but you want to serve 18, you need 18/24 = 3/4 of each ingredient. GCF(18, 24) = 6, so 18/24 → 3/4. Multiply all quantities by 3/4.

GCF in Real-World Applications

Beyond fraction simplification, GCF solves several types of practical problems:

Equal group distribution: You have 36 apples and 48 oranges to pack into baskets, with each basket containing the same number of each fruit and no fruit left over. The maximum number of baskets is GCF(36, 48) = 12. Each basket gets 3 apples and 4 oranges.

Tile/grid problems: You want to tile a 120cm × 180cm floor with identical square tiles, minimizing waste. The largest square tile that works perfectly has side length GCF(120, 180) = 60 cm. You need (120/60) × (180/60) = 2 × 3 = 6 tiles.

Scheduling: Event A repeats every 12 days, Event B every 18 days. They next occur together after LCM(12, 18) = 36 days. GCF(12, 18) = 6 tells you the unit cycle; LCM = 12×18/6 = 36.

Cryptography: RSA encryption requires choosing two large primes p and q. The public key n = p×q and Euler's totient φ(n) = (p-1)(q-1). For the algorithm to work securely, the encryption exponent e must be coprime to φ(n) — i.e., GCF(e, φ(n)) = 1. Coprimality is verified using the Euclidean algorithm.

The Euclidean Algorithm: History and Proof

The Euclidean algorithm, described in Euclid's Elements (Book VII, Proposition 2, c. 300 BC), is one of the oldest algorithms in mathematics — predating most of modern mathematics by over two millennia. It remains in widespread computational use today, testament to its elegance and efficiency.

The algorithm: To find GCF(a, b) where a > b: divide a by b, get quotient q and remainder r. Then GCF(a, b) = GCF(b, r). Repeat until r = 0; the last non-zero remainder is the GCF.

Why it works: If d divides both a and b, then d divides a − q×b = r. Conversely, if d divides both b and r, then d divides b×q + r = a. So the set of common divisors of (a, b) equals the set of common divisors of (b, r). Their GCFs must be equal.

Efficiency: In the worst case (consecutive Fibonacci numbers), the algorithm takes O(log(min(a,b))) steps. GCF(F(n+1), F(n)) requires exactly n steps — this is why consecutive Fibonacci numbers are called the "worst case" for the Euclidean algorithm. For GCF(144, 89): 144 = 1×89 + 55; 89 = 1×55 + 34; 55 = 1×34 + 21; 34 = 1×21 + 13; 21 = 1×13 + 8; 13 = 1×8 + 5; 8 = 1×5 + 3; 5 = 1×3 + 2; 3 = 1×2 + 1; 2 = 2×1 + 0. GCF = 1. (10 steps, as expected for F(12)/F(11).)

GCF vs LCM: Key Differences and Connections

GCF (Greatest Common Factor) and LCM (Least Common Multiple) are complementary operations. Understanding when to use each is essential for fraction arithmetic.

To add fractions 1/12 + 1/18: find LCM(12, 18) = 36. Convert: 3/36 + 2/36 = 5/36. To simplify 12/18: find GCF(12, 18) = 6. Divide: 2/3.

Extended Euclidean Algorithm and Bézout's Identity

The extended Euclidean algorithm not only computes GCF(a, b) but also finds integers x and y such that ax + by = GCF(a, b). This is Bézout's Identity, and the integers x and y are called Bézout coefficients. This has critical applications in modular arithmetic and cryptography.

Example: Find x and y such that 24x + 36y = GCF(24, 36) = 12. Working backward through the Euclidean algorithm steps: 12 = 24 − 1×12 = 24 − 1×(36 − 1×24) = 2×24 − 1×36. So x = 2, y = -1. Verify: 24×2 + 36×(−1) = 48 − 36 = 12 ✓.

The modular inverse of a modulo m exists if and only if GCF(a, m) = 1. If it exists, it can be found using the extended Euclidean algorithm. For example, the inverse of 7 mod 11: GCF(7, 11) = 1 (coprime), so the inverse exists. 7×8 = 56 = 5×11 + 1 ≡ 1 (mod 11), so 7⁻¹ ≡ 8 (mod 11). This is foundational to RSA decryption and many cryptographic operations.

GCF for Fractions, Ratios, and Proportions

GCF is indispensable when working with ratios and proportions in everyday contexts. A ratio like 48:64 can be simplified by dividing both terms by GCF(48, 64) = 16, giving the equivalent ratio 3:4. This simplification makes comparisons easier and reveals the underlying relationship.

In baking and cooking, recipes often need to be scaled. If a recipe calls for 450g flour and 300g sugar, the ratio is 450:300. GCF(450, 300) = 150. Simplified ratio: 3:2. For any batch size, use flour and sugar in a 3:2 ratio.

Map scales use ratios. A scale of 1:50,000 means 1 map unit = 50,000 real units. If you want to express a measurement of 150cm on map as a real distance of 75,000cm, simplify 150:75,000. GCF(150, 75000) = 150. Simplified: 1:500. So the map scale is 1:500 for that measurement.