GCD & LCM Calculator

Two answers to two different questions

The greatest common divisor is the largest number that divides all of your inputs. The least common multiple is the smallest number all of them divide into. GCD is about breaking things down and is always at most the smallest input; LCM is about building up and is always at least the largest. Reaching for the wrong one is the usual mistake, and the giveaway is direction: reducing a fraction needs GCD, finding a common denominator needs LCM.

Euclid's algorithm

The fastest way to a GCD does not require factorising anything. Divide the larger number by the smaller, replace the larger with the remainder, and repeat until the remainder is zero; the last non-zero remainder is the GCD. For 48 and 18: 48 mod 18 is 12, 18 mod 12 is 6, 12 mod 6 is 0, so the answer is 6. This is around 2,300 years old and is still what production code uses, because it is fast even on numbers far too large to factorise.

The relationship between them

For any two numbers, GCD × LCM equals the product of the numbers. So once you have the GCD, the LCM follows by dividing the product by it — which is how calculators avoid computing the LCM directly. The identity holds only for pairs; with three or more numbers you must apply it iteratively rather than multiplying everything together.

Coprime numbers

When the GCD is 1, the numbers share no factor other than 1 and are called coprime or relatively prime. They need not be prime themselves — 8 and 9 are coprime while neither is prime. Their LCM is simply their product, since there is nothing shared to remove. Coprimality underpins modular arithmetic and RSA key generation, where the public exponent must be coprime to a particular derived value.

Where each one shows up

GCD reduces fractions, scales ratios down and computes aspect ratios — 1920 and 1080 share a GCD of 120, which is how you get 16:9. LCM finds common denominators, works out when two repeating events coincide, and sizes buffers that must divide evenly into several block sizes. The classic LCM problem — two buses leaving every 12 and 18 minutes meet again after 36 — is the shape of most real uses.

Edge cases worth knowing

The GCD of any number and 0 is that number, since everything divides 0. The LCM of anything with 0 is 0. Negative inputs are conventionally handled by taking absolute values, since divisibility ignores sign.