GCD, LCM, Permutations, and Combinations Explained

GCD, LCM, permutations, and combinations all rest on the same building block — factorials and division — applied in different combinations.

GCD and LCM: related by one clean identity

The greatest common divisor (GCD) of 12 and 18 is 6 (the largest number dividing both evenly). The least common multiple (LCM) is 36 (the smallest number both divide into evenly). These aren't independently calculated — LCM(a,b) = (a×b)/GCD(a,b), so once you know the GCD, the LCM formula is immediate: (12×18)/6 = 216/6 = 36, confirming the identity.

How the Euclidean algorithm finds GCD without factoring

Rather than factoring both numbers (which gets slow for large numbers), the Euclidean algorithm repeatedly replaces the larger number with the remainder of dividing it by the smaller, until the remainder hits zero. For 12 and 18: 18 mod 12 = 6, then 12 mod 6 = 0 — the last non-zero remainder (6) is the GCD, found in just two steps regardless of how large the original numbers were.

Permutations: order matters

nPr = n! / (n−r)!. Choosing and arranging 3 items from 10, where order matters: 10P3 = 10!/7! = 10×9×8 = 720 distinct ordered arrangements.

Combinations: order doesn't matter

nCr = n! / (r!(n−r)!). Choosing 3 items from 10 where order doesn't matter: 10C3 = 10!/(3!×7!) = 720/6 = 120 — exactly 1/6th of the permutation count, because each group of 3 can be internally arranged in 3! = 6 different orders, all of which count as the same combination.

Common mistakes to avoid

• Using the permutation formula when order genuinely doesn't matter (like picking a committee) — this overcounts by a factor of r!
• Forgetting that 0! is defined as 1, not 0, which trips up formulas at their boundary cases
• Assuming GCD only applies to two numbers — the same algorithm extends to any number of values by applying it pairwise

Calculate your own values with the GCD & LCM calculator, permutation & combination calculator, and factorial calculator.