GCD and LCM Puzzles

Two lighthouses flash every 18 seconds and every 24 seconds respectively, both flashing together at time zero. How many seconds until they next flash together? This is a least-common-multiple question in disguise, and it's typical of a puzzle family — scheduling, tiling, fraction problems — that becomes fast and mechanical once you recognize the GCD/LCM structure and use the identity connecting them, rather than listing out multiples by hand.

The core idea: GCD measures shared structure, LCM measures shared timing

The greatest common divisor, $\gcd(a,b)$, is the largest number dividing both $a$ and $b$ exactly — it captures what two numbers have "in common" as building blocks. The least common multiple, $\text{lcm}(a,b)$, is the smallest number both $a$ and $b$ divide into exactly — it captures when two repeating cycles next align. They're linked by one identity worth memorizing:

$$\gcd(a,b) \times \text{lcm}(a,b) = a \times b .$$

In plain English: the product of the two numbers splits exactly into "what they share" times "how far apart their cycles need to run before syncing up again." This means you only ever need to compute one of $\gcd$ or $\text{lcm}$ directly (via Euclid's algorithm, which is fast even for large numbers) and can get the other for free by dividing $a \times b$ by it.

Worked example 1: the lighthouses

Find $\gcd(18, 24)$ using Euclid's algorithm: $24 = 1 \times 18 + 6$, then $18 = 3 \times 6 + 0$ — the last nonzero remainder is 6, so $\gcd(18,24) = 6$. By the identity, $\text{lcm}(18,24) = \dfrac{18 \times 24}{6} = \dfrac{432}{6} = 72$. So the lighthouses next flash together after 72 seconds — verified by checking that 72 is a multiple of both 18 ($72 = 4 \times 18$) and 24 ($72 = 3 \times 24$), and it's the smallest such number since 6 is the largest shared factor.

Worked example 2: a tiling puzzle using GCD

A rectangular floor measures 42 feet by 30 feet, and you want to tile it exactly with the largest possible square tiles, no cutting. The largest square that tiles both dimensions evenly has side length $\gcd(42, 30)$. Euclid's algorithm: $42 = 1 \times 30 + 12$, then $30 = 2 \times 12 + 6$, then $12 = 2 \times 6 + 0$ — so $\gcd(42,30) = 6$. The largest tile is $6 \times 6$ feet, giving $\frac{42}{6} \times \frac{30}{6} = 7 \times 5 = 35$ tiles exactly, with none cut — a direct physical reading of what "greatest common divisor" means: the biggest unit that both dimensions are whole multiples of.

What this means in practice

GCD/LCM reasoning shows up any time an interview question involves repeating cycles (settlement dates, coupon payments, rebalancing schedules that happen every $m$ and every $n$ periods) or exact-division constraints (splitting a position into equal lots, tiling, batch sizing). Euclid's algorithm is also worth knowing as a general mental-math speed tool: it's far faster than factoring large numbers to find their GCD, especially under interview time pressure.