GCD and LCM with Explanation

Enter two numbers — you get the GCD and LCM with full working: the Euclidean algorithm step by step, the LCM formula via the GCD, and an alternative check via prime factorization.

Why GCD and LCM matter. The GCD (greatest common divisor) is what you reduce fractions with: divide the numerator and denominator by their GCD. The LCM (least common multiple) is what you need for a common denominator. The Euclidean algorithm finds the GCD in a few divisions even for large numbers — it is one of the oldest algorithms in mathematics, over two thousand years old.

FAQ

What is the GCD in simple words?

The greatest common divisor is the largest number both numbers divide by evenly. For 48 and 36 the common divisors are 1, 2, 3, 4, 6, 12 — the largest is 12, and that is the GCD.

What is the LCM in simple words?

The least common multiple is the smallest number divisible by both. For 4 and 6 it is 12: no smaller number divides by both 4 and 6. The handy formula: the product of the numbers divided by their GCD.

How does the Euclidean algorithm work?

Divide the larger number by the smaller and take the remainder. Then divide the smaller by that remainder — and repeat until the remainder is zero. The last non-zero remainder is the GCD. It works because the common divisors of (a, b) are exactly the common divisors of (b, a mod b).

Where are GCD and LCM used in practice?

The main school use is fractions: GCD for reducing, LCM for the common denominator. Beyond that — recurring-events problems (“buses leave every 12 and 18 minutes — when do they meet?” is an LCM question), simplifying ratios and proportions.