Calculator
Greatest common divisor and least common multiple of two integers, computed with the Euclidean algorithm.
What is in here
Calculators
Six calculators that run entirely in this browser. Inputs are validated, so a rejected entry says what is wrong instead of returning a confident wrong answer.
Number theory
Greatest common divisor and least common multiple, computed exactly - the LCM is arbitrary-precision, so large coprime inputs stay correct.
Commas or spaces, up to 12 values. Anything that is not a whole number is named back rather than coerced.
The greatest common divisor of two integers is the largest integer dividing both of them. The calculator uses the Euclidean algorithm, which repeatedly replaces the larger number by its remainder on division by the smaller until the remainder is zero. The last non-zero remainder is the greatest common divisor, and the method finishes in a handful of steps even for very large inputs.
The least common multiple is the smallest positive integer both numbers divide. It follows from the greatest common divisor: the product of the two numbers divided by their greatest common divisor. Working through the divisor first is what keeps the arithmetic small.
Two integers are coprime, or relatively prime, when their greatest common divisor is 1. That is the condition for a modular inverse to exist, so this calculator and the modular arithmetic one answer two halves of the same question. Values are handled as arbitrary precision integers, so inputs longer than a machine word are exact rather than rounded.
Worked example
a = 48, b = 18gcd(48, 18) = 6, lcm(48, 18) = 144Euclid: 48 = 2 x 18 + 12, 18 = 1 x 12 + 6, 12 = 2 x 6 + 0. The lcm is 48 x 18 / 6 = 144.
Questions
It replaces the pair (a, b) with (b, a mod b) and repeats until the second number is zero. The first number at that point is the greatest common divisor, because every common divisor of a and b is also a common divisor of b and a mod b.
For positive integers a and b, gcd(a, b) multiplied by lcm(a, b) equals a multiplied by b. So the least common multiple is the product divided by the greatest common divisor.
Two integers are coprime when their greatest common divisor is 1, meaning they share no prime factor. Coprimality is exactly the condition under which a has a multiplicative inverse modulo b.