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.