# GCD and LCM: Euclid’s 2,300-year-old shortcut, and when two buses meet again

> The greatest common divisor simplifies fractions, and the least common multiple tells you when repeating things line up again. This guide shows how to find both by hand, why Euclid’s method is so fast, and the one identity that links them.

Published 2026-10-08 by Toolcloak. 4 minute read. Original: https://toolcloak.pages.dev/articles/gcd-and-lcm-euclids-2300-year-old-shortcut-and-when-two-buses-meet-again
Related free tool: [GCD & LCM Calculator](https://toolcloak.pages.dev/tools/gcd-lcm-calculator)

Two small ideas hide behind most fraction homework and a surprising amount of real scheduling. The **greatest common divisor** (GCD, also called HCF) is the biggest number that divides two numbers exactly. The **least common multiple** (LCM) is the smallest number that both of them divide into. One tells you how to shrink, the other how to align.

> **In short**
> - GCD(48, 18) = **6** and LCM(48, 18) = **144**.
> - The two are linked: **GCD × LCM = a × b**. Check: 6 × 144 = 864 = 48 × 18.
> - Euclid’s method finds the GCD by repeated remainders: **GCD(a, b) = GCD(b, a mod b)** until the remainder is 0.
> - Use the **GCD to simplify fractions** (48/18 = 8/3) and the **LCM to line up repeating events** (every 12 and 18 minutes → every 36).

## Divisors you can see

A divisor of a number divides it with no remainder. The divisors of 48 are 1, 2, 3, 4, 6, 8, 12, 16, 24 and 48. The divisors of 18 are 1, 2, 3, 6, 9 and 18. The ones that appear in both lists are the **common divisors**: 1, 2, 3 and 6. The largest of them, 6, is the GCD.

**Divisors of 48 and 18, and what they share**

|  | Count |
| --- | --- |
| Divisors of 48 | 10 |
| Divisors of 18 | 6 |
| Common divisors | 4 (1, 2, 3, 6) |

*Listing divisors works for small numbers, but it gets slow quickly. The next two methods do not need long lists.*

**GCD as a tiling: a 48 × 18 rectangle in 6 × 6 squares**

| Group | Count |
| --- | --- |
| Squares of side 6 | 8 across × 3 down = 24 |

*The GCD is the side of the largest square that tiles a rectangle exactly. A 48 × 18 floor needs 24 square tiles of side 6.*

Try it: [GCD & LCM Calculator](https://toolcloak.pages.dev/tools/gcd-lcm-calculator). Enter two or more numbers and get the GCD, LCM and the working.

## Method 1: prime factors

Break each number into primes. 48 = 2⁴ × 3 and 18 = 2 × 3². For the GCD take the **smaller** power of each prime that both have. For the LCM take the **larger** power of every prime that appears.

| Prime | In 48 | In 18 | GCD uses (smaller) | LCM uses (larger) |
| --- | --- | --- | --- | --- |
| 2 | 2⁴ | 2¹ | 2¹ = 2 | 2⁴ = 16 |
| 3 | 3¹ | 3² | 3¹ = 3 | 3² = 9 |
| Product |  |  | 2 × 3 = 6 | 16 × 9 = 144 |

*The smaller powers give the GCD (6) and the larger powers give the LCM (144).*

> **GCD × LCM = a × b:** For any two positive numbers, the GCD times the LCM equals their product. For 48 and 18: 6 × 144 = 864 = 48 × 18. This is the easiest way to get the LCM after you have the GCD: LCM = a × b ÷ GCD.

## Method 2: Euclid’s algorithm

Written around 300 BC in Euclid’s Elements, this is one of the oldest algorithms still in everyday use. The idea: any number that divides both a and b also divides the remainder of a ÷ b. So replace the pair (a, b) by the smaller pair (b, remainder), and repeat until the remainder is zero. The last non-zero number is the GCD.

**GCD of 1071 and 462**

1. **1071 = 2 × 462 + 147.** Remainder 147, so now find GCD(462, 147).
2. **462 = 3 × 147 + 21.** Remainder 21, so now find GCD(147, 21).
3. **147 = 7 × 21 + 0.** Remainder 0. The last non-zero number, 21, is the GCD.

**Euclid shrinks the numbers fast (pair sizes)**

| Step | Amount |
| --- | --- |
| Start: 1071 | 1,071 |
| Next big number | → 462 |
| Then | → 147 |
| Then | → 21 |

*Each step replaces the bigger number by a much smaller remainder: 1071 → 462 → 147 → 21. Three divisions are enough.*

**How few steps Euclid needs**

|  | Value | Note |
| --- | --- | --- |
| GCD(123456, 7890) | 7 | Six-digit numbers, a handful of divisions |
| GCD(1000000, 999999) | 2 | Neighbours finish at once |
| GCD of two Fibonacci numbers | 28 | The slowest possible case |

*The worst cases are consecutive Fibonacci numbers, as proved by Gabriel Lamé in 1844. Even then, the step count grows with the number of digits, not the size of the numbers.*

See the [Fibonacci article](https://toolcloak.pages.dev/articles/the-fibonacci-sequence-from-rabbits-to-the-golden-ratio-and-why-slow-code-loves-it) for why those numbers are the slowest: each remainder is exactly the previous Fibonacci number, so the sequence shrinks as slowly as it can.

## The GCD in action: simplifying fractions

To reduce a fraction to its simplest form, divide the top and bottom by their GCD. For 48/18 the GCD is 6, so 48 ÷ 6 = 8 and 18 ÷ 6 = 3, giving 8/3. Using the GCD guarantees the answer is fully reduced in one step; dividing by 2 and then by 3 would take two.

**Reducing 48/18**

| Guessing small factors | Divide by the GCD |
| --- | --- |
| 2 steps | 1 step |
| 48/18 → 24/9 | GCD(48, 18) = 6 |
| 24/9 → 8/3 | 48 ÷ 6 = 8, 18 ÷ 6 = 3 |
| Easy to stop too early | Always fully simplified |

*Both reach 8/3. The GCD makes sure you never stop one step short.*

## The LCM in action: when things line up again

Two buses leave a stop together. One returns every 12 minutes, the other every 18. They next leave together at the LCM of 12 and 18, which is 36 minutes. The same idea schedules shifts, mixed repeating tasks and gear teeth that must return to the same pairing.

**Bus A (every 12 min) and bus B (every 18 min)**

| When | What |
| --- | --- |
| 0 min | Both leave together. The starting point. |
| 12 min | Bus A again. Bus B is still on its way. |
| 18 min | Bus B again. Bus A is waiting for its next trip. |
| 24 min | Bus A again. Still not together. |
| 36 min | Both leave together. LCM(12, 18) = 36. The pattern repeats from here. |

**LCM of different pairs: smaller cycles meet sooner**

|  | Minutes |
| --- | --- |
| 4 and 6 | 12 |
| 6 and 10 | 30 |
| 12 and 18 | 36 |
| 8 and 15 | 120 |
| 7 and 13 | 91 |

*When the two numbers share no common factor (7 and 13), the LCM is simply their product, 91. The more they share, the sooner they meet.*

> **Three or more numbers:** Apply the idea one pair at a time: LCM(4, 6, 10) = LCM(LCM(4, 6), 10) = LCM(12, 10) = 60. Three tasks that repeat every 4, 6 and 10 days all fall on the same day every 60 days. The same works for the GCD.

## Quick practice

1. GCD of 84 and 36? 84 = 2 × 36 + 12, 36 = 3 × 12, so **12**.
2. LCM of 84 and 36? 84 × 36 ÷ 12 = **252**.
3. Simplify 84/36. Divide both by 12 to get **7/3**.
4. Are 35 and 64 coprime? GCD(35, 64) = **1**, so yes. Their LCM is 2,240.

Two numbers with GCD 1 are called coprime. Coprime numbers matter in encryption, where choosing keys depends on them. Read about it in [prime numbers and RSA](https://toolcloak.pages.dev/articles/prime-numbers-why-they-thin-out-and-why-your-bank-depends-on-them).

## Frequently asked questions

### What is the GCD of 48 and 18?

6. It is the largest number that divides both 48 and 18 exactly.

### Are GCD and HCF the same thing?

Yes. HCF (highest common factor) and GCD (greatest common divisor) are different names for the same number.

### How do you find the LCM from the GCD?

LCM(a, b) = a × b ÷ GCD(a, b). For 48 and 18 that is 864 ÷ 6 = 144.

### What is the Euclidean algorithm?

A method that replaces (a, b) with (b, a mod b) over and over until the remainder is 0. The last non-zero value is the GCD.

### What if the GCD is 1?

Then the numbers are coprime (relatively prime). Their LCM is just their product.

### Where is the LCM used in everyday life?

Adding fractions with different denominators, scheduling repeating events, and gear or rotation problems all use the LCM.