← All guides

GCD and LCM in seconds, and what they are for

Find the greatest common divisor and least common multiple with prime factors or Euclid's algorithm, and use them to simplify fractions.

The greatest common divisor (GCD) is the largest whole number that divides both numbers. The least common multiple (LCM) is the smallest number both divide into. Here are two ways to find them, using 84 and 120.

Method 1: prime factors

Break each number into primes:

84 = 2² · 3 · 7  ·  120 = 2³ · 3 · 5
  • GCD: take the primes they share, with the smaller power: 2² · 3 = 12.
  • LCM: take every prime that appears, with the larger power: 2³ · 3 · 5 · 7 = 840.

Method 2: Euclid's algorithm

For large numbers, factoring is slow. Instead, keep dividing and replacing the larger number with the remainder:

120 = 1 · 84 + 36
84 = 2 · 36 + 12
36 = 3 · 12 + 0

When the remainder reaches 0, the last divisor is the GCD: 12.

The shortcut between them

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

12 × 840 = 10 080 = 84 × 120. ✓ Once you have the GCD, the LCM is a × b ÷ GCD.

Where you will use them

  • Simplifying fractions: divide top and bottom by the GCD. 84/120 becomes 7/10.
  • Adding fractions: the LCM of the denominators is the lowest common denominator. 1/84 + 1/120 = 10/840 + 7/840 = 17/840.
  • Schedules and cycles: two buses leaving every 84 and 120 minutes leave together again after 840 minutes.
Try it in Andulator

Solve → Number theory · GCD & LCM

  1. Open Solve and choose Number theory · GCD & LCM.
  2. Enter the two whole numbers a and b.
  3. Tap Calculate. Prime factors has its own tool in the same list.
Keep reading