About the GCD & LCM Calculator

The GCD and LCM calculator computes the greatest common divisor and least common multiple of any set of positive integers. The GCD is the largest integer that divides every number in the set without remainder, while the LCM is the smallest positive integer that is a multiple of every number in the set. Together they form the foundation of number theory and appear in everything from cryptography to musical harmony.

The GCD is most often used to simplify fractions: dividing the numerator and denominator by their GCD gives the fraction in lowest terms. The LCM is most often used to find a common denominator when adding or subtracting fractions, or to schedule events that recur on different cycles (for example, two buses that arrive every 12 and 18 minutes will next coincide at the LCM of 36 minutes).

This calculator accepts any number of inputs separated by commas, spaces, or newlines. It uses the Euclidean algorithm, which is both fast and exact even for very large numbers, and it displays the relationship GCD x LCM = product of the two numbers so you can verify the result for the two-number case.

How It Works

The GCD of two numbers is computed using the Euclidean algorithm, which repeatedly replaces the larger number by the remainder of dividing the two numbers until the remainder is zero:

gcd(a, b):
  while b is not zero:
    (a, b) = (b, a mod b)
  return a

For more than two numbers, the GCD is computed iteratively by folding the operation: gcd(a, b, c) = gcd(gcd(a, b), c). The LCM is related to the GCD by the formula:

lcm(a, b) = (a * b) / gcd(a, b)

This formula works because the GCD captures the prime factors shared by both numbers, and dividing the product by the GCD removes the double-counting of those shared factors. For more than two numbers, the LCM is also computed by folding: lcm(a, b, c) = lcm(lcm(a, b), c).

The Euclidean algorithm is remarkably efficient. Its worst-case number of divisions is proportional to the number of digits in the smaller input, which means even thousand-digit numbers can be processed in a fraction of a second. This is why GCD-based methods underpin the RSA cryptosystem, where finding the GCD of two enormous numbers is a routine step in key generation.

Worked Examples

Using the default input 12, 18, 24, the GCD is the largest number dividing all three. The divisors of 12 are 1, 2, 3, 4, 6, 12; of 18 are 1, 2, 3, 6, 9, 18; of 24 are 1, 2, 3, 4, 6, 8, 12, 24. The common divisors are 1, 2, 3, and 6, so the GCD is 6. Using the Euclidean algorithm: gcd(12, 18) = gcd(18, 12) = gcd(12, 6) = gcd(6, 0) = 6, then gcd(6, 24) = gcd(24, 6) = gcd(6, 0) = 6.

The LCM is the smallest number that is a multiple of all three. The multiples of 12 are 12, 24, 36, 48, 60, 72...; of 18 are 18, 36, 54, 72...; of 24 are 24, 48, 72... The smallest common multiple is 72. Using the formula: lcm(12, 18) = 12 * 18 / 6 = 36, then lcm(36, 24) = 36 * 24 / gcd(36, 24) = 864 / 12 = 72.

Notice that for the two-number case 12 and 18, the product of GCD and LCM equals the product of the inputs: 6 * 36 = 216 = 12 * 18. This relationship holds for any pair of integers and is a useful check on your arithmetic.

When to Use This Tool

Use the GCD and LCM calculator when you need to:

Simplify fractions by dividing numerator and denominator by their GCD.
Find a common denominator before adding or subtracting fractions.
Schedule recurring events that have different periods (bus timetables, alarms, deliveries).
Tile a rectangular floor with square tiles of the largest possible size.
Determine the fundamental period of combined oscillating signals.
Work through number theory exercises in a discrete mathematics course.
Verify intermediate results in RSA key generation or other cryptographic routines.

Limitations & Disclaimer

This calculator accepts positive integers only and rejects zero, negative, or non-integer inputs. The LCM of a large set of numbers can grow very quickly and may exceed JavaScript's safe integer range (approximately 9 * 10^15), at which point precision is lost. For cryptographic or arbitrary-precision work, use a dedicated big-integer library. See our disclaimer for full details.

Frequently Asked Questions

What is the difference between GCD and LCM?

The GCD (greatest common divisor) is the largest integer that divides every input without remainder, while the LCM (least common multiple) is the smallest positive integer that is a multiple of every input. The GCD measures shared factors; the LCM measures a common multiple.

How does the Euclidean algorithm work?

It repeatedly replaces the larger number by the remainder when the two numbers are divided. The last non-zero remainder is the GCD. This process is fast because each step reduces the numbers substantially, and it terminates when one of them reaches zero.

Can the inputs be negative?

The GCD is defined for integers, and gcd(a, b) = gcd(|a|, |b|), so the sign does not affect the result. This calculator filters inputs to positive integers to keep the LCM well-defined, since the LCM is conventionally a positive quantity.

How many numbers can I enter?

Any number. The calculator folds the GCD and LCM operations across all inputs, so entering 12, 18, 24, 30 gives a single GCD and a single LCM for the whole set. Separate numbers with commas, spaces, or newlines.

What is the relationship between GCD and LCM?

For any two positive integers a and b, the product of the GCD and the LCM equals the product of the two numbers: gcd(a, b) * lcm(a, b) = a * b. This is because the GCD captures the shared prime factors and the LCM captures each distinct prime factor at its highest power.

Why is the LCM useful for scheduling?

If two events recur every a and b units of time, they next coincide after lcm(a, b) units of time. The LCM gives the smallest time at which both cycles align, which is exactly what you need when planning deliveries, shifts, or maintenance intervals.

Last updated: July 21, 2026 · Author: HT99 Tools Editorial Team · Reviewed by: HT99 Tools Editorial Team