GCD / LCM Ladder

Who This Is For

Use this ladder when gcd/lcm problems stop being one-line formulas and start turning into feasibility, construction, or prime-exponent reasoning tasks.

Warm-Up

• gcd and lcm identities
• prime-exponent view of gcd/lcm

Core

• gcd/lcm construction conditions
• repeated gcd or lcm operation reasoning
• Bézout coefficients when the statement asks for witnesses

Retrieval Layer

• one Bézout witness or composite-mod inverse -> Modular Arithmetic hot sheet
• congruence merge after gcd-consistency reasoning -> Chinese Remainder hot sheet
• exact repo note -> Euclid Problem
• starter primitive -> extended-gcd-diophantine.cpp

Example Notes

• Euclid Problem
• Common Divisors
• GCD on Blackboard
• CRYPTKEY

Exit Criteria

You are ready to move on when you can:

• explain gcd/lcm using prime exponents instead of only formulas
• spot overflow-safe lcm code patterns
• tell when a construction problem is really per-prime reasoning
• connect these tasks back to number-theory basics instead of treating them as isolated tricks

External Practice

• CP-Algorithms - Euclidean Algorithm
• USACO Guide - Divisibility

Tutorial Link

• GCD / LCM