GCD and LCM Calculator with Euclidean Steps

About the GCD and LCM Calculator

The GCD and LCM Calculator finds the greatest common divisor and the least common multiple of two or more integers and shows how it got there. The greatest common divisor, also called the greatest common factor (GCF) or highest common factor (HCF), is the largest whole number that divides every input exactly. The least common multiple is the smallest positive number that every input divides. For two integers the page also gives the Bézout coefficients, two integers x and y with a·x + b·y = gcd(a, b).

Type the integers separated by commas, spaces or new lines. Negative numbers and zero are accepted, and the integers can be as long as 1,000 digits each, with up to 100 of them. Arithmetic is exact, so a 300-digit result comes out digit for digit. Everything runs in your browser and the numbers you type are never sent anywhere.

How to use it

How the answers are found

The Euclidean algorithm repeatedly divides the larger number by the smaller and keeps the remainder. When the remainder reaches zero, the last non-zero remainder is the greatest common divisor. For 1071 and 462 the page shows:

$$\begin{aligned} 1071 &= 2 \times 462 + 147 \\ 462 &= 3 \times 147 + 21 \\ 147 &= 7 \times 21 + 0 \end{aligned}$$

so gcd(1071, 462) = 21. The number of steps grows only with the number of digits, which is why even 1,000-digit integers finish at once.

The least common multiple follows from the greatest common divisor:

$$\operatorname{lcm}(a, b) = \frac{|a \times b|}{\gcd(a, b)}$$

For 12 and 18 that is 216 / 6 = 36. If any input is zero, the least common multiple is 0.

More than two integers are folded one at a time: gcd(12, 18, 30) = gcd(gcd(12, 18), 30) = gcd(6, 30) = 6, and in the same way lcm(12, 18, 30) = lcm(36, 30) = 180. The steps box shows each stage.

Bézout coefficients come from the extended Euclidean algorithm, which keeps track of how each remainder is built from the two inputs. For 240 and 46 it gives 240 × (−9) + 46 × 47 = 2. These coefficients are what you need to find a modular inverse: when gcd(a, m) = 1, the coefficient of a is its inverse modulo m.

Worked examples

• gcd(48, 36) is 12 and lcm(48, 36) is 144.
• 35 and 64 are coprime: their greatest common divisor is 1, and the page says so.
• gcd(−12, 0) is 12, because every integer divides 0, and lcm(−12, 0) is 0.
• Fractions: to simplify 462/1071, divide both parts by gcd = 21 to get 22/51.

Privacy

Every calculation runs in your browser. Nothing is uploaded, and nothing is kept once you close the tab.

Related tools

To see the prime factors behind a greatest common divisor, use the Prime Factorization Calculator: the GCD is the product of the shared prime powers, and the LCM is the product of the highest powers. The Prime Number Generator lists and tests primes, and the Number List Calculator adds up and averages a list of numbers.

Open-source credits

• The calculator is written for this site and uses no third-party library. Arithmetic uses the browser's built-in BigInt, specified in ECMA-262.
• The greatest common divisor uses the Euclidean algorithm from Euclid's Elements, book VII, propositions 1 and 2, and the Bézout coefficients use the extended Euclidean algorithm as given in Donald Knuth's The Art of Computer Programming, volume 2, section 4.5.2. The worked example 1071 and 462 is the standard textbook case.

Frequently asked questions