GCD & LCM Calculator

Calculate the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) with complete Euclidean algorithm steps. Supports two or more numbers.

What is GCD & LCM Calculator?

The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) are two of the most important concepts in elementary number theory, with applications from simplifying fractions in middle school to cryptographic algorithms that secure the internet.

The Euclidean algorithm, described by Euclid around 300 BC, is one of the oldest and most efficient algorithms in mathematics. It computes the GCD in O(log(min(a,b))) steps, terminating rapidly even for very large numbers. The algorithm applies the identity: GCD(a, b) = GCD(b, a mod b) repeatedly until the remainder is zero.

This calculator shows the complete Euclidean algorithm step by step for two numbers, and also computes GCD and LCM for lists of multiple numbers using the generalization: GCD(a, b, c) = GCD(GCD(a, b), c).

Formula

Euclidean Algorithm:

GCD(a, b) = GCD(b, a mod b) until b = 0

LCM from GCD:

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

For multiple numbers:

GCD(a, b, c) = GCD(GCD(a, b), c)

LCM(a, b, c) = LCM(LCM(a, b), c)

How to Calculate

Enter two positive integers a and b.
Apply integer division: a = q×b + r.
Replace a with b and b with r. Repeat until r = 0.
The last non-zero remainder is the GCD.
Compute LCM = |a × b| / GCD using the fundamental identity.
Use Multiple Numbers mode for three or more numbers.

Example

Find GCD(48, 18): 48 = 2×18 + 12 → 18 = 1×12 + 6 → 12 = 2×6 + 0. GCD = 6. LCM = |48×18|/6 = 864/6 = 144. Check: 144/48 = 3 ✓, 144/18 = 8 ✓.

Key Terms Explained

GCD: Largest integer dividing both numbers without remainder
LCM: Smallest positive integer divisible by both numbers
Co-prime: Two numbers with GCD = 1, sharing no common prime factors
Euclidean algorithm: Ancient algorithm computing GCD by repeated division
Modulo operation: a mod b is the remainder when a is divided by b
Divisibility: a divides b if b/a has no remainder

Common Use Cases

Simplifying fractions: reduce a/b by dividing both by GCD(a, b)
Adding fractions with different denominators: find LCM of denominators
Scheduling: finding when two recurring events will next coincide
RSA key generation: checking that exponent e is co-prime with φ(n)
Gear ratio problems in mechanical engineering
Tile pattern design: finding the smallest repeating unit

Frequently Asked Questions

What is GCD and how is it calculated?

GCD (Greatest Common Divisor) is the largest positive integer that divides both a and b without remainder. The Euclidean algorithm computes it efficiently: repeatedly replace (a, b) with (b, a mod b) until b = 0. The last non-zero value is the GCD.

What is LCM and what is it used for?

LCM (Least Common Multiple) is the smallest positive integer divisible by both a and b. It is used for adding fractions with different denominators, scheduling problems, and music theory.

What is the relationship between GCD and LCM?

GCD(a, b) × LCM(a, b) = |a × b|. Once you know the GCD, the LCM is simply |a × b| / GCD(a, b). This is more efficient than listing multiples.

What does co-prime mean?

Two numbers are co-prime (relatively prime) if their GCD is 1 — they share no common prime factors. Co-primality is fundamental in modular arithmetic, cryptography, and the Chinese Remainder Theorem.

Related Tools