---
title: "GCD and LCM Calculator with Euclid's Steps | Prime Orchard"
description: "Find the greatest common divisor and least common multiple of two or more numbers, with every step of Euclid's algorithm and Bézout's identity."
url: https://primeorchard.top/gcd-lcm-calculator/
---

GCD & LCM

# GCD and LCM calculator

The greatest common divisor and least common multiple of two to ten whole numbers, with Euclid's algorithm written out step by step.

GCD (HCF) 42

LCM 1,260

The largest number that divides 84, 126 and 210 exactly is 42.

### Euclid's algorithm, step by step

#### Step 1: gcd(84, 126)

1. 126= 1 × 84+ 42
2. 84= 2 × 42+ 0

The last non-zero remainder is the GCD: **42**.

#### Step 2: gcd(42, 210)

1. 210= 5 × 42+ 0

The last non-zero remainder is the GCD: **42**.

### LCM from the GCD

1. lcm(84, 126) = 84 × 126 ÷ 42 = 252
2. lcm(252, 210) = 252 × 210 ÷ 42 = 1,260

### Check with prime factors

- 84 = 22 × 3 × 7
- 126 = 2 × 32 × 7
- 210 = 2 × 3 × 5 × 7

The GCD takes each prime to its *lowest* power in the list: 2 × 3 × 7 = 42. The LCM takes each prime to its *highest* power: 22 × 32 × 5 × 7 = 1,260.

## Two ways to the same answer

The **greatest common divisor** (GCD, also called the highest common factor) is the largest number that divides every number in your list exactly. The **least common multiple** (LCM) is the smallest positive number that all of them divide into.

**Euclid's algorithm** finds the GCD without factoring anything. Divide the larger number by the smaller and keep the remainder, then divide the last divisor by that remainder, and repeat until the remainder is 0. The last divisor is the GCD. It works because anything that divides a and b also divides a − q × b, the remainder. It is fast as well: the number of steps grows only with the number of digits.

1071 = 2 × 462 + 147 → 462 = 3 × 147 + 21 → 147 = 7 × 21 + 0, so gcd = 21

For three or more numbers the steps are chained, gcd(a, b, c) = gcd(gcd(a, b), c), and the LCM follows from lcm(a, b) = a × b ÷ gcd(a, b), chained the same way.

With small numbers you can also compare **prime factorizations**: the GCD keeps each shared prime at its lowest power, the LCM keeps every prime at its highest. The calculator adds that check when all numbers are below 1015.

## Sources

- Euclid, *Elements*, Book VII, [Proposition 2](https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/propVII2.html) (finding the greatest common measure), in David E. Joyce's online edition.
- Knuth DE. *The Art of Computer Programming*, Vol. 2, §4.5.2 (the greatest common divisor), and [Euclidean algorithm](https://en.wikipedia.org/wiki/Euclidean_algorithm) on step counts and Bézout's identity.

## Questions

**What does coprime mean?**

Numbers are coprime when their GCD is 1, like 8 and 15; neither has to be prime. A list can be coprime while some pairs share a factor: 6, 10 and 15 have GCD 1, yet each pair shares 2, 3 or 5.

**What are the GCD and LCM when one number is 0?**

gcd(n, 0) = n, because every number divides 0, and lcm(n, 0) = 0. gcd(0, 0) is written as 0 by convention.

**Where are GCD and LCM used?**

Simplifying fractions (divide top and bottom by the GCD), adding fractions (the LCM of the denominators is the lowest common denominator), lining up repeating cycles such as gear teeth or timetables, and RSA cryptography, which uses Bézout's coefficients to build keys.