Guide: Least Common Multiple (LCM)
What is LCM?
The least common multiple (LCM) is the smallest positive integer that is divisible by two or more integers. For example LCM(12, 18) = 36, because 36 is the smallest number divisible by both 12 and 18 without a remainder. LCM is particularly useful when adding and subtracting fractions with different denominators.
How to calculate LCM?
The simplest method is to use the relationship LCM(a, b) = (a * b) / GCD(a, b). Simply multiply the numbers and then divide by their GCD. For example: LCM(12, 18) = (12 * 18) / GCD(12, 18) = 216 / 6 = 36. This formula is fast and efficient for any integers.
Properties of LCM
LCM(a, b) * GCD(a, b) = a * b (the product of LCM and GCD equals the product of the numbers). LCM(a, b) is always a multiple of both numbers a and b. LCM(a, b) is always greater than or equal to each of the numbers. If a divides b, then LCM(a, b) = b.
Practical Applications
LCM is essential when adding fractions - first we find the LCM of the denominators to equalize them. In scheduling, LCM determines when two cyclic events will occur simultaneously. In cryptography, LCM is used when generating RSA keys. In computer science, LCM is used to synchronize processes and determine common time intervals.
Buses every 7 and 11 minutes coincide least often of all
The least common multiple answers a question people meet constantly without naming it: when do two repeating things happen together? Two intervals that share a factor line up quickly; two that share nothing line up only after their product. Seven and eleven minutes coincide every seventy-seven — the worst case there is.
How it works
- Finds the least common multiple of two or more numbers.
- Answers the recurrence question directly: how long until two cycles align again.
- Uses the greatest common divisor, since the two quantities are linked by an exact identity.
LCM(a, b) = a × b ÷ GCD(a, b) and therefore GCD(a, b) × LCM(a, b) = a × b when GCD = 1 the numbers are coprime and the LCM is the full product
Worked example
Two services running at different intervals, and how often they meet.
- every 12 and 18 minutes → together every 36 (GCD 6)
- every 15 and 20 minutes → together every 60 (GCD 5)
- every 10 and 12 minutes → together every 60 (GCD 2)
- every 7 and 11 minutes → together every 77 (GCD 1)
The more the intervals share, the sooner they align. 12 and 18 share a factor of 6 and meet every 36 minutes; 7 and 11 share nothing and meet only every 77 — the product itself.
Reading the result
- The identity GCD × LCM = a × b is worth remembering because it makes either quantity easy once you have the other. For 12 and 18, the product is 216 and the GCD is 6, so the LCM must be 36 without further work.
- Coprime numbers are the worst case for coincidence and the best case for coverage. That is why gear teeth counts are often chosen to be coprime: the same pair of teeth then meets as rarely as possible, spreading wear evenly.
- Two gears of 12 and 18 teeth return to their starting alignment after 36 tooth-engagements, which is 3 turns of the small gear and 2 of the large. The LCM gives the cycle length and division gives each wheel's share of it.
- The GCD is the other half of the same tool, and it reduces fractions. 84/126 shares a divisor of 42, so it reduces in one step to 2/3 — the GCD is exactly how far a fraction can be simplified.
Common questions
- When will two recurring events next happen together?
- After the LCM of their intervals, counted from the last time they coincided. Twelve-minute and eighteen-minute cycles meet every thirty-six minutes; if they have never yet coincided, they align at the first common multiple after both have started.
- Why does sharing a factor make things align sooner?
- Because the shared factor is already common ground. LCM = a × b ÷ GCD, so a larger GCD divides the product down further. 12 and 18 share 6, which cuts 216 to 36; 7 and 11 share nothing, so nothing is cut.