GCD, LCM & modular arithmetic
Overview
Fundamental number theory algorithms: Greatest Common Divisor (Euclidean algorithm), Least Common Multiple, and math under a modulus.
Many competitive programming or math-heavy algorithms require computing divisors quickly or preventing integer overflow when answering 'modulo 10^9 + 7'.
Where used: Cryptography (RSA), Hashing functions, Handling extremely large numbers in algorithms
Why learn this
- The Euclidean algorithm is one of the oldest and most elegant algorithms in computer science.
- Modular arithmetic is essential to prevent overflow in languages with fixed-size integers.
- GCD and LCM often appear in puzzle-style interview questions.
Common mistakes
- Applying modulo at the end instead of every step: If a problem asks for `(A * B) % M`, and `A * B` overflows your language's integer limit, computing `(A * B)` first will crash. You must apply the modulo rules during the operations: `((A % M) * (B % M)) % M`.
- Wrong LCM formula: LCM(a, b) is `(a * b) / GCD(a, b)`. If you compute `a * b` first, it might overflow. Better to compute `a / GCD(a, b) * b`.
Recall questions
- What is the time complexity of the Euclidean algorithm for GCD(a, b)?
- How do you safely compute LCM(a, b) to avoid intermediate overflow?
Understanding checks
What is the sequence of calls when finding `gcd(48, 18)` using the Euclidean algorithm `gcd(a, b) = gcd(b, a % b)`?
gcd(48, 18) -> gcd(18, 12) -> gcd(12, 6) -> gcd(6, 0). Returns 6.
Each step replaces `a` with `b`, and `b` with the remainder of `a / b`. When `b` is 0, `a` is the GCD.
In modular addition, is `(A + B) % M` always equal to `((A % M) + (B % M)) % M`?
Yes.
Addition and multiplication are distributive over the modulo operator. This property allows us to keep intermediate values small.
Practice tasks
Water Jug Problem
Determine if it's possible to measure exactly `targetCapacity` liters using two jugs with capacities `x` and `y`. (Hint: use GCD).
Continue learning
Previous: Big-O Notation