Maths SolverThe greatest common divisor of two integers, $\gcd(a, b)$, is the largest integer that divides both of them. The least common multiple, $\mathrm{lcm}(a, b)$, is the smallest positive integer that they both divide. They are both standard secondary-school content, and they are both computed in school by the same painful method: list every prime factor of both numbers, then take products of the right ones.
That method works, but it is slow, error-prone, and unnecessary. There is an algorithm for the GCD that is over two thousand years old and considerably faster than prime factorisation. Once you have the GCD, the LCM is one division.
The Euclidean algorithm
Take two positive integers $a$ and $b$ with $a \ge b$. Replace $a$ with the remainder $a \bmod b$. Swap and repeat. The procedure stops when $b$ becomes $0$; at that point $a$ is the GCD. That is the entire algorithm.
A worked example for $\gcd(252, 105)$:
$$252 = 2 \cdot 105 + 42$$ $$105 = 2 \cdot 42 + 21$$ $$42 = 2 \cdot 21 + 0$$
The last non-zero remainder is $21$, so $\gcd(252, 105) = 21$. Three steps. Try doing that with prime factorisation in three steps.
Why it works
The key fact is: any number that divides both $a$ and $b$ also divides $a - kb$ for any integer $k$. So the common divisors of $a$ and $b$ are exactly the same set as the common divisors of $a \bmod b$ and $b$. Each step of the algorithm replaces a pair with a smaller pair that shares the same GCD; the numbers shrink rapidly until one of them reaches zero, at which point the other one is the answer.
From GCD to LCM
There is a simple identity: for any two positive integers,
$$\gcd(a, b) \times \mathrm{lcm}(a, b) = a \times b.$$
So once you have the GCD, the LCM is just $\tfrac{a \cdot b}{\gcd(a, b)}$. For our example: $\mathrm{lcm}(252, 105) = \tfrac{252 \cdot 105}{21} = \tfrac{26460}{21} = 1260$.
Why both quantities matter
The GCD is what you divide by when you simplify a fraction; that is covered in Simplifying fractions, properly. The LCM is what you find when you add two fractions: $\tfrac{a}{m} + \tfrac{b}{n}$ becomes a single fraction over $\mathrm{lcm}(m, n)$, which is the smallest denominator that works for both. Using the LCM here keeps the numbers small; you can also use $mn$ as a common denominator and then simplify, but the resulting arithmetic is harder.
Three or more numbers
Both functions extend by associativity:
$$\gcd(a, b, c) = \gcd(\gcd(a, b), c), \qquad \mathrm{lcm}(a, b, c) = \mathrm{lcm}(\mathrm{lcm}(a, b), c).$$
So $\gcd(12, 18, 30)$ is $\gcd(\gcd(12, 18), 30) = \gcd(6, 30) = 6$. The identity $\gcd \cdot \mathrm{lcm} = ab$ does not generalise to three numbers, so do not try to compute the LCM of three numbers from the GCD.
The mistakes I see most often
1. Confusing GCD with LCM
The GCD is at most the smaller of the two numbers; the LCM is at least the larger. If you compute “$\gcd(8, 12) = 24$,” that is the LCM, not the GCD. Always sanity-check by size.
2. Forgetting the “divides exactly” condition
A common divisor must divide each number with no remainder. $4$ is a common divisor of $8$ and $12$; $5$ is not, even though it is close to several factors. There is no “close enough” in divisibility.
3. Computing prime factorisations when you do not need them
For two numbers, the Euclidean algorithm is faster, especially when both are large. Save prime factorisation for problems that genuinely need it — primality testing, modular arithmetic, simplifying surds.
Where this comes up later
Modular arithmetic, ratios, ratios in chemistry (mole ratios, dilutions), gear ratios in mechanics, scheduling problems (“both events recur every X and Y days; when do they coincide?”), and almost every operation involving fractions. The LCM of two periodic events is when they next align; the GCD of two ratios is what you divide by to put them in simplest form.
References
- Euclid, Elements, Book VII, Propositions 1–2 (the original statement of the algorithm, around 300 BCE).
- Wikipedia: Euclidean algorithm, Least common multiple.
- Khan Academy: Factors and multiples.