Greatest Common Factor (GCF) Calculator

The Greatest Common Factor (GCF), also called the Greatest Common Divisor (GCD), is the largest positive integer that divides two or more numbers without leaving a remainder. It is fundamental in simplifying fractions, solving Diophantine equations, and many areas of number theory.

Methods to find GCF:

Method 1: Prime Factorization:

1. Find all prime factors of each number
2. Identify factors common to all numbers
3. Multiply the shared prime factors together (using the lowest power of each)

Method 2: Euclidean Algorithm (most efficient): GCF(a, b) = GCF(b, a mod b) repeated until the remainder is 0 The last non-zero remainder is the GCF.

What each variable means:

• a, b: the two (or more) numbers whose GCF you want
• mod: the remainder after integer division (e.g., 48 mod 18 = 12)
• Prime factors: the prime numbers that multiply together to give the original number

Worked example: Prime Factorization: Find GCF(180, 252):

• 180 = 2² × 3² × 5
• 252 = 2² × 3² × 7
• Common factors: 2² and 3² (5 and 7 are not shared)
• GCF = 2² × 3² = 4 × 9 = 36

Worked example: Euclidean Algorithm: GCF(252, 180):

• 252 = 1 × 180 + 72 → GCF(180, 72)
• 180 = 2 × 72 + 36 → GCF(72, 36)
• 72 = 2 × 36 + 0 → remainder is 0; GCF = 36 ✓

Practical applications:

• Simplifying fractions: 180/252 → divide both by 36 → 5/7
• Tiling: What is the largest square tile that perfectly covers a 180 cm × 252 cm floor? Answer: 36 cm × 36 cm tiles (exactly 5 × 7 = 35 tiles)
• Scheduling: Two buses depart at different intervals; GCF tells when they next depart together
• Cryptography: GCF is the foundation of the RSA encryption algorithm (checking co-primality)

LCM relationship: GCF(a, b) × LCM(a, b) = a × b. So LCM(180, 252) = (180 × 252) / 36 = 1,260.

Why the Euclidean algorithm wins. Prime factorization is the method taught first because it explains what a common factor is, but it is the slower of the two by a wide margin. To factor a number you have to hunt for its primes, and for anything with large prime factors that hunt is genuinely hard. The Euclidean algorithm never factors anything. It just takes remainders, and each step shrinks the numbers so quickly that GCF(1234567890, 987654321) finishes in about a dozen lines. That speed is exactly why it sits inside RSA key generation, where the numbers are hundreds of digits long and factoring them is the thing the whole system assumes nobody can do.

Enter whole numbers only. A decimal gets truncated, since a greatest common factor is a question about integers. Zeros are ignored rather than treated as errors, because every number divides zero evenly and including one would tell you nothing.