CodeWithYash

Foundation · Module 2 · Lesson 1

GCD & LCM

Euclidean algorithm and divisibility.

15–25 min readLesson 7 of 123

Lesson 7 of 123

1d streak

Theory lesson · Step-by-step

Understand GCD & LCM

Euclidean algorithm and divisibility.

Worked approach

Trace the reasoning step by step

  1. 1Keep the larger value as a and the smaller as b.
  2. 2Replace (a, b) with (b, a mod b).
  3. 3Repeat until b becomes zero.
  4. 4The remaining a is the GCD; derive LCM with |a × b| / GCD.

Concrete example

Find gcd(48, 18) and lcm(48, 18).

  1. 148 mod 18 = 12
  2. 218 mod 12 = 6
  3. 312 mod 6 = 0

gcd = 6 and lcm = 48 × 18 / 6 = 144.

What must remain true (Loop Invariant)

gcd(a, b) = gcd(b, a mod b), so each remainder preserves the answer.

Cost Model

Complexity & Trade-offs

Euclidean algorithm
O(log min(a,b))
O(1)
Remainders shrink rapidly.

When to use it

  • Counting, divisibility, modular cycles, masks, and overflow-safe arithmetic.
  • Replacing simulation with a mathematical identity.
  • Encoding compact state for search and dynamic programming.

Common mistakes

  • Using an identity without checking its domain or overflow behavior.
  • Forgetting how the language handles negative remainder and signed shifts.
  • Confusing value magnitude with the number of input values.

Practice prompts

  • Reproduce the worked GCD & LCM example without looking at the trace.
  • Change one input condition and explain whether the GCD & LCM invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.