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.
What GCD and LCM calculation is
The greatest common divisor (GCD) is the largest integer that divides two integers evenly, and the least common multiple (LCM) is the smallest integer among the common multiples of two integers. Enter two positive integers and this tool works out both values instantly using the Euclidean algorithm, and it also shows the working step by step — dividend, divisor, quotient and remainder.
By hand the usual route is to factorise into primes and look for the common factors, but the larger the numbers grow, the more laborious that factorisation becomes. The Euclidean algorithm this tool uses finds the greatest common divisor through nothing but repeated division, so integers with many digits go through exactly the same procedure. Input is limited to integers of 1 or above; enter zero, a negative number or a decimal and no result is shown.
How to use the GCD and LCM calculator
- Enter number A Type the first positive integer whose greatest common divisor and least common multiple you want.
- Enter number B Type the other positive integer. Which of A and B is the larger makes no difference to the result.
- Check the result The greatest common divisor (GCD) and the least common multiple (LCM) appear automatically.
- Follow the working Each step of the Euclidean algorithm (dividend = divisor × quotient + remainder) is laid out as a table, so you can follow the procedure through until the remainder reaches zero.
Tips for getting more out of it
- 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.
When GCD and LCM calculation comes in useful
Groundwork for reducing a fraction
Find the greatest common divisor of the numerator and denominator and dividing both by it reduces the fraction. If you want to see the reduced result itself, a fraction calculator with a reduce function is handy.
Working out when several cycles coincide
If one thing happens every 3 days and another every 5, the next time they fall on the same day is 15 days later — the least common multiple of 3 and 5. It applies to arranging shift and event cycles.
Checking maths homework and exam practice
You can immediately verify whether the greatest common divisor or least common multiple you worked out by hand is right, working included.
Preparing to find a common denominator
When putting several fractions with different denominators over a common denominator, the least common multiple of those denominators becomes the new shared one.
Grasping the basics behind cryptography
Computing greatest common divisors underpins modern cryptography, RSA key generation among other things, so following the working is a useful first step towards understanding how it operates.
Terms used here
- Greatest common divisor (GCD)
- The largest of the integers that divide two or more integers evenly, known as their common divisors.
- Least common multiple (LCM)
- The smallest of the multiples shared by two or more integers, known as their common multiples.
- Euclidean algorithm
- An algorithm that looks at the remainder when the larger number is divided by the smaller, then repeats the same operation on the pair of divisor and remainder to find the greatest common divisor. It takes its name from the work of the ancient Greek mathematician Euclid.
- Coprime
- Said of two integers whose greatest common divisor is 1. The least common multiple of two coprime numbers is simply the two multiplied together.
- Prime factorisation
- Breaking an integer down into a product of primes. Greatest common divisors and least common multiples can also be found from the combination of shared prime factors, though for large numbers the Euclidean algorithm is faster.
- Common divisor and common multiple
- A common divisor is a divisor shared by several integers; a common multiple is a multiple shared by them. The greatest common divisor and least common multiple are the largest and smallest of each.
Frequently Asked Questions
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.