LCM & GCD Calculator

The Greatest Common Divisor (GCD), also called the Greatest Common Factor (GCF), and the Least Common Multiple (LCM) are two fundamental operations in number theory. They appear constantly in fractions, scheduling, tiling, and cryptography.

GCD: The largest number that divides both A and B evenly. LCM: The smallest positive number that is divisible by both A and B.

The key relationship between GCD and LCM: LCM(A, B) = (A × B) / GCD(A, B)

Finding GCD using the Euclidean Algorithm: Repeatedly apply: GCD(A, B) = GCD(B, A mod B) until remainder = 0.

Worked example: Find GCD(48, 18): GCD(48, 18) → 48 mod 18 = 12 → GCD(18, 12) GCD(18, 12) → 18 mod 12 = 6 → GCD(12, 6) GCD(12, 6) → 12 mod 6 = 0 → GCD = 6

LCM(48, 18) = (48 × 18) / 6 = 864 / 6 = 144

Worked example 2: GCD(56, 98): 98 mod 56 = 42 → GCD(56, 42) 56 mod 42 = 14 → GCD(42, 14) 42 mod 14 = 0 → GCD = 14 LCM(56, 98) = (56 × 98) / 14 = 392

Real-world applications:

• Fractions: To add ½ + ⅓, find LCM(2,3) = 6 → convert to 3/6 + 2/6 = 5/6
• Scheduling: Two buses depart every 8 and 12 minutes. LCM(8,12) = 24. They sync every 24 minutes.
• Tiling: To tile a 48×18 floor with square tiles and no cutting, GCD(48,18) = 6, so the largest tile that works is 6×6. That takes 8 tiles along the 48 side and 3 along the 18 side, 24 tiles in all.
• Music: Rhythm patterns of 3 and 4 beats align every LCM(3,4) = 12 beats

Prime factorization, the other route. The Euclidean algorithm is faster, but factorization shows why the answers come out as they do. Break each number into primes, then take the lowest power of each shared prime for the GCD and the highest power of every prime that appears for the LCM:

48 = 2⁴ × 3 and 18 = 2 × 3². GCD takes 2¹ × 3¹ = 6. LCM takes 2⁴ × 3² = 144.

Every prime present in either number has to be present in the LCM at its largest power, or one of the two numbers would not divide it. The calculator shows both factorizations so you can check this by eye.