Greatest Common Divisor and Least Common Multiple

Finds the greatest common divisor of two integers with the Euclidean algorithm, and the least common multiple as the product ÷ the GCD.

Explanation

For two positive integers, the greatest common divisor (GCD) is the largest number that divides both, and the least common multiple (LCM) is the smallest number that both divide into.

The GCD comes from the Euclidean algorithm: divide the larger by the smaller, replace the pair with the divisor and the remainder, and repeat until the remainder is 0. The last value left is the GCD. It is far quicker than listing every divisor of both numbers.

Once you have the GCD, the LCM follows immediately.

\mathrm{lcm}(a, b) = \dfrac{a \times b}{\gcd(a, b)}

$a$ , $b$ — integers of 1 or more
$\gcd(a, b)$ — the greatest common divisor
$\mathrm{lcm}(a, b)$ — the least common multiple

Example

Take $a = 12$ and $b = 18$ . The algorithm runs:

$18 \div 12 = 1$ remainder $6$
$12 \div 6 = 2$ remainder $0$

The remainder has reached zero, so the GCD is 6. The LCM is then

\dfrac{12 \times 18}{6} = \dfrac{216}{6} = 36

Notes

Both inputs must be integers of 1 or more. Decimals and non-positive values are rejected.
By hand, divide before you multiply and the numbers stay small: $\dfrac{12}{6} \times 18 = 36$ never touches 216 at all.
When two numbers are coprime, meaning their GCD is 1, the LCM is simply their product.
If one number is a multiple of the other, the GCD is the smaller number and the LCM is the larger.