Why compute lcm as a / gcd(a, b) * b instead of a * b / gcd(a, b)?
answer
- Both forms agree in exact arithmetic
- Ask what the biggest intermediate value is
- The product can dwarf the final answer
- The gcd divides a with no remainder
- Divide first, multiply second
basics
~20 sBoth forms are mathematically equal, but the product a * b can overflow a fixed-width integer before the division ever runs. Dividing first is exact, because the gcd divides a, and keeps every intermediate no larger than the answer.
solid answer
~50 sFor positive `a` and `b`, `gcd(a, b) * lcm(a, b) = a * b`, so the lcm is `a * b / gcd(a, b)`. In exact arithmetic the two orderings agree; in fixed-width machine arithmetic they do not. Take two recurring jobs firing every 45000 and every 60000 minutes: their next coincidence is at `lcm = 180000`, a tiny number, but `a * b` is 2.7 billion, which does not fit a 32-bit signed integer. Computing `a / gcd(a, b) * b` gives `45000 / 15000 * 60000 = 180000` with no intermediate above the result. The division is exact — never truncating — because `gcd(a, b)` divides `a` by definition, so reordering costs nothing in accuracy. One honest caveat: this removes a *spurious* overflow only. If the true lcm itself exceeds the range, no ordering saves you, and you need a wider type or a bound check.
go deeper
Remember that the lcm comes from the gcd through gcd(a, b) times lcm(a, b) equals a times b, and that the safe way to write it divides before multiplying.
Explain that the two orderings differ only in the size of the intermediate value, and justify why dividing by the gcd first is exact rather than merely convenient.
Show how the naive ordering fails silently in production — a wrong coincidence time rather than a crash — and name the guards you would add: zero inputs, absolute values, and a bound check for an lcm that genuinely does not fit.
Own the policy question: where arithmetic like this must be centralised in one reviewed helper rather than re-derived per service, and when a workload justifies moving to arbitrary-precision arithmetic instead of defending fixed widths case by case.
## The identity, and why the ordering is not cosmetic For positive integers, `gcd(a, b) * lcm(a, b) = a * b`. The reason is factor bookkeeping: for each prime, the gcd takes the **minimum** exponent appearing in `a` and `b`, and the lcm takes the **maximum**. Minimum plus maximum equals the sum of the two exponents, which is what the product `a * b` carries. So the lcm is the product with the shared part divided out once: `lcm(a, b) = a * b / gcd(a, b)`. On paper, `a * b / g` and `a / g * b` are the same number. On a machine with fixed-width integers they are not the same computation, because the first one forms `a * b` as a real intermediate value, and that intermediate can exceed the representable range even when the final answer is small. ## A concrete scheduling case Two recurring jobs fire every `a = 45000` minutes and every `b = 60000` minutes, and you want the first minute at which they coincide. That minute is the lcm. `gcd(45000, 60000) = 15000`, so `lcm = 45000 / 15000 * 60000 = 3 * 60000 = 180000` minutes. Now compare the intermediates: | Expression | Largest intermediate | Fits 32-bit signed range (about 2.147e9)? | |---|---|---| | `a * b / g` | 2,700,000,000 | No — the product overflows before dividing | | `a / g * b` | 180,000 | Yes — no intermediate exceeds the answer | The answer these jobs need is 180000, a number that would fit in a 16-bit value with room to spare. The naive ordering destroys it anyway, and in a silently-wrapping arithmetic it does not fail loudly: it produces a plausible-looking wrong minute, so the two jobs are scheduled to "coincide" at a time they never do. This class of defect surfaces as a scheduling anomaly weeks later, not as a crash. ## Why dividing first is exact A reasonable worry about reordering integer arithmetic is truncation: integer division discards a remainder, so moving a division earlier usually changes the result. Here it cannot, because `gcd(a, b)` divides `a` by the very definition of a common divisor. The division `a / g` has remainder 0, so no information is lost, and the subsequent multiplication by `b` reconstructs exactly the value `a * b / g`. Reordering is safe *specifically because the divisor is a divisor*; the same trick would be invalid with an arbitrary denominator. As a bonus, `a / g` is the part of `a` not shared with `b`, so the expression reads as "take the non-shared part of `a`, then step it by `b`" — the same reasoning you would use out loud. Mainstream runtimes made genuinely different calls on what happens when the naive ordering overflows: fixed-width integers in ecosystems such as Java and C wrap around or invoke undefined behaviour with no signal, while Python and Ruby promote automatically to arbitrary-precision integers, where the naive ordering is merely slower rather than wrong. The ordering discipline is therefore a portability habit as much as a correctness one — the same expression is a silent corruption in one environment and a harmless inefficiency in another. ## Edge cases worth stating before you are asked - **A zero input.** `lcm(a, 0)` is conventionally 0, and `gcd(0, 0) = 0`, which makes the division blow up. Guard the zero case explicitly rather than trusting the formula. - **Negative inputs.** The clean statement of the identity is `gcd(a, b) * lcm(a, b) = |a * b|`. Normalise to absolute values before you start. - **The result itself is too big.** Reordering bounds the intermediates by the answer, not by the type. Three jobs at large mutually coprime periods can produce an lcm beyond any fixed width; then you need a wider type, arbitrary precision, or a documented cap. - **More than two numbers.** The lcm of a list folds pairwise, `lcm(lcm(x, y), z)`, and each fold should use the divide-first ordering — otherwise you have simply moved the overflow to the middle of the loop, where it is harder to spot. ## What an interviewer is testing The question is not really about the lcm formula, which most candidates can state. It is about whether you notice that a mathematically-irrelevant reordering is an operationally significant one, and whether you can justify the reordering as *exact* rather than merely "safer". A candidate who says "I'd use a bigger type" has a valid fallback but has skipped the free fix; the strong answer gives the reordering, the exactness argument, and the honest limit of what it buys.
- Why is moving the division earlier safe, when integer division normally truncates?Because the divisor here is a divisor of the numerator: gcd(a, b) divides a by definition, so a / gcd(a, b) has remainder 0 and loses nothing. Multiplying that exact quotient by b reconstructs a * b / gcd(a, b) precisely. The same reordering with an arbitrary denominator would truncate and be wrong.
- Does the divide-first ordering make lcm computation overflow-proof?No. It bounds every intermediate by the final answer, which removes overflows that were purely an artefact of the ordering. If the true lcm itself exceeds the type's range — easy with several large mutually coprime periods — no ordering helps. At that point you need a wider representation or an explicit bound check that fails loudly.
- How do you extend this to the lcm of a whole list of periods?Fold pairwise: keep a running value and replace it with lcm(running, next), using the divide-first ordering at every step. The lcm is associative, so the order of the list does not matter. Watch the running value carefully — it grows fast, so a bound check inside the loop is worth more than one at the end.
saying these in an interview costs you the question
- Says the two orderings are identical because algebra says so
- Claims dividing first truncates and loses precision
- Believes the reordering makes lcm overflow-proof
- States gcd times lcm equals a plus b
- Forgets to guard a zero input before dividing by the gcd