Skip to main content

GCD and LCM, Explained: Euclidean Steps, Fractions, and Scheduling

A practical guide to computing GCD and LCM by hand and online: the Euclidean algorithm, the LCM = a×b/GCD shortcut, fraction reduction, and overlap scheduling.

Published By Li Lei
#math #gcd #lcm #number-theory #euclidean-algorithm

GCD and LCM, Explained: From Euclidean Steps to Real Schedules

Two of the most useful numbers in elementary number theory are the greatest common divisor (GCD) and the least common multiple (LCM). The GCD of a set is the largest integer that divides every member with no remainder. The LCM is the smallest positive integer that every member divides into. One is about what numbers share; the other is about the smallest place they meet again.

Most people first see these in a fractions chapter and never touch them again. That is a shame, because the same two ideas reduce fractions, find common denominators, predict when two repeating events collide, and size gear ratios. If you want the answer right now, the GCD & LCM Calculator takes a list like 12, 18, 30 and returns both values along with the working. The rest of this post is about understanding what it shows you.

The Euclidean Algorithm: GCD by Repeated Remainder

The slow way to find a GCD is to list every divisor of each number and pick the biggest one they share. For 48 and 36 that is doable; for 999983 and 524287 it is hopeless. The Euclidean algorithm, written down around 300 BCE, does the same job in a handful of steps.

The rule is a single line: replace the larger number with the remainder of dividing it by the smaller one, then repeat. Each step is a = q·b + r, where q is the quotient and r is the remainder. You drop a, keep b, and the new remainder r becomes the next divisor. When the remainder reaches 0, the last non-zero divisor is the GCD.

Watch it run on 48 and 36:

  • 48 = 1 × 36 + 12
  • 36 = 3 × 12 + 0

The remainder hit 0, and the last divisor before that was 12. So GCD(48, 36) = 12. Two steps, no guessing, no factoring. The reason it works is that any number dividing both a and b must also divide the remainder r, so the common divisors never change as you shrink the pair — but the numbers themselves keep getting smaller until one of them cleanly divides the other.

LCM = a × b ÷ GCD

Once you have the GCD, the LCM falls out almost for free. For any two positive integers a and b:

LCM(a, b) = (a × b) / GCD(a, b)

Carry on with our example. The product 48 × 36 = 1728, and we already know the GCD is 12, so:

LCM(48, 36) = 1728 / 12 = 144

So LCM(48, 36) = 144. Here is a detail worth copying into your own code: divide before you multiply. Computing a / GCD(a, b) × b keeps the intermediate value small, which matters once your inputs are large. Multiply first and a pair of big coprime numbers can overflow a 64-bit integer before the division ever has a chance to shrink it. The calculator runs everything on BigInt and divides first, so 15-digit inputs stay exact instead of drifting into floating-point error.

One caution: this identity is a two-number relationship. People try to stretch it to GCD × LCM = a × b × c for three numbers, and it simply does not hold. For 4, 6, and 8 the GCD is 2 and the LCM is 24, but 2 × 24 = 48, while the product is 192. For three or more numbers, work from the prime factorizations instead — GCD takes the lowest power of each shared prime, LCM takes the highest power of every prime that appears.

Reducing Fractions and Finding Common Denominators

The most common everyday use is fractions, and it cuts both ways.

To reduce a fraction, divide the numerator and denominator by their GCD. Take 360/420. The GCD is 60, so 360/420 = (360 ÷ 60)/(420 ÷ 60) = 6/7. Fully reduced in one division. The Euclidean step table makes the 60 visible — 420 = 1×360 + 60, then 360 = 6×60 + 0 — which is exactly what a teacher means by "show your working."

To add fractions with unlike denominators, use the LCM of the denominators as your common denominator. For 5/12 + 7/18, the LCM of 12 and 18 is 36. Rewrite each fraction over 36: 5/12 = 15/36 and 7/18 = 14/36, so the sum is 29/36. You could also use 12 × 18 = 216, and you would still get a correct fraction — just an ugly one that needs reducing afterward. The LCM gives you the smallest denominator that works, so the answer comes out close to lowest terms already.

I keep a small mental note from grading homework years ago: half the wrong fraction answers came from "adding the denominators." 1/12 + 1/18 is not 2/30. The denominators are not data you sum; they are scales you have to align first. The LCM is the alignment.

Scheduling: When Repeating Events Line Up

The LCM answers a question that comes up far outside a math class: given several things that repeat on fixed intervals, when do they all happen at once?

Bus A leaves every 12 minutes and Bus B every 18 minutes, both at 8:00. Their next shared departure is LCM(12, 18) = 36 minutes later — 8:36 — and then every 36 minutes after that. The same shape covers cron jobs ("one runs every 15 minutes, one every 20 — when do they collide?" → LCM 60, so once an hour) and machinery (gear teeth meshing back to their starting alignment).

It scales past pairs, too. Say you run a report every 6 days, a backup every 8 days, and an audit every 9 days, all starting today. The next day all three land together is LCM(6, 8, 9) = 72 days out. The prime-factor view shows why it stretches that far: 6 = 2·3, 8 = 2³, 9 = 3², so the LCM must include 2³ and 3², giving 8 × 9 = 72. The backup's factor of 8 is the thing pushing the cycle out. If you would rather look up these factor rules than rederive them, the math formula reference collects the divisibility and factorization facts in one place.

Doing It by Hand vs. Doing It Fast

For two small numbers, the Euclidean algorithm on paper is genuinely quick — usually two or three lines. For a set of numbers, large inputs, or any time you want the prime factorization laid out next to the answer, a tool that shows every step saves the tedium without hiding the method. That is the balance worth aiming for: understand the algorithm well enough to trust the result, then let the machine grind through the arithmetic exactly.

The short version to remember:

  • GCD = largest shared divisor; find it with repeated remainders (the Euclidean algorithm).
  • LCM = smallest shared multiple; for two numbers, a × b ÷ GCD, dividing before multiplying.
  • Use the GCD to reduce; use the LCM for common denominators and overlap timing.

Type your numbers into the GCD & LCM Calculator, read the Euclidean step table, and you will see the same two-line proof we walked through above — for whatever values you actually care about.

Made by Toolora · Updated 2026-06-13