GCD & LCM Calculator

Greatest Common Divisor

The GCD is the largest number that divides both inputs evenly. It is also called the Greatest Common Factor (GCF) or Highest Common Factor (HCF).

Example: GCD(12, 18) = 6

Divisors of 12: 1, 2, 3, 4, 6, 12

Divisors of 18: 1, 2, 3, 6, 9, 18

Common: 1, 2, 3, 6 → Greatest is 6

Least Common Multiple

The LCM is the smallest number that both inputs divide into. It is essential for adding fractions with different denominators.

Example: LCM(4, 6) = 12

Multiples of 4: 4, 8, 12, 16, 20...

Multiples of 6: 6, 12, 18, 24...

The Euclidean Algorithm

An efficient way to find the GCD without listing all divisors:

1. Divide the larger number by the smaller
2. Replace the larger with the remainder
3. Repeat until the remainder is 0
4. The last non-zero value is the GCD

Real-World Applications

• Simplifying fractions: Divide both parts by GCD
• Scheduling: LCM finds when events coincide (e.g., two buses arriving at the same stop at the same time)
• Tiling: GCD determines the largest square tile for a rectangular floor
• Music: LCM helps find when rhythmic patterns sync up

Key Relationship

GCD(a, b) × LCM(a, b) = a × b

This identity lets you find one if you know the other.