GCD & LCM Calculator

Enter two positive integers to find their greatest common divisor (GCD) using the Euclidean algorithm, with each step of the calculation shown. The least common multiple (LCM) is calculated at the same time.

Greatest Common Divisor (GCD)
Least Common Multiple (LCM)

Euclidean Algorithm Steps

Formula
= × +

What is the Euclidean algorithm?

The Euclidean algorithm is a classic method for finding the greatest common divisor of two integers. The procedure: take the remainder of the larger number divided by the smaller number, then repeat the same operation with the divisor and that remainder. When the remainder reaches 0, the divisor at that point is the greatest common divisor. This lets you find the GCD of even very large numbers accurately in relatively few steps. It's recorded in Euclid's "Elements" from around 300 BC, making it one of the oldest algorithms still in use today.

Tips

  • The least common multiple (LCM) can be found with the formula "A × B ÷ GCD." It's commonly used when finding a common denominator for fractions, or figuring out when several events with different periods will align.
  • If two numbers are coprime (their GCD is 1), their LCM is simply A × B.
  • A practical advantage of the Euclidean algorithm is that it can compute the GCD of large numbers faster than going through prime factorization.
  • The order in which you enter the two numbers doesn't affect the result — the calculation automatically starts from the larger of the two.

Frequently Asked Questions

The GCD is the largest integer that divides both numbers evenly, while the LCM is the smallest number that's a multiple of both. For example, for 12 and 18, the GCD is 6 and the LCM is 36.

Finding the GCD via prime factorization takes longer as numbers get larger, since factorization itself becomes more expensive. The Euclidean algorithm, by contrast, only needs repeated division and remainder calculations, so it can find the GCD of even very large integers quickly.

This tool only supports positive integers. If you enter 0, a negative number, or a decimal, no result will be shown.

This tool handles two numbers at a time. For three or more, you can apply it pairwise (e.g. find the GCD of A and B, then find the GCD of that result and C) to get the same answer.
ツールくん

Side Note — why a 2,000-year-old algorithm is still in daily use

The Euclidean algorithm appears in Book VII of Euclid's "Elements," written by the ancient Greek mathematician around 300 BC. It's considered one of the oldest algorithms on record, and more than two thousand years later, it remains one of the first algorithms introduced in computer science textbooks.

The reason it has endured so long comes down to its computational efficiency. Mathematically, the number of steps the Euclidean algorithm requires is proven to be roughly proportional to the number of digits in the input (the worst case occurs with pairs of numbers related to the Fibonacci sequence), meaning it can find the GCD of even enormous integers in a practical amount of time.

Modern cryptography — RSA encryption, for instance — still uses GCD computation (or its extended form, the extended Euclidean algorithm) during key generation. It's a striking illustration of the universality of mathematics that an ancient discovery underpins part of the technology securing the internet today.

More tools in this category