Stage 1 · Code
Bit Manipulation, Math & Randomization
GCD, LCM and Modular Arithmetic
Euclid’s algorithm, cycle alignment, and modular fast power for the large-number arithmetic that appears everywhere in interviews.
Why Number Theory Matters in Programming
Bit tricks help with representation, but many interview and systems problems are really about arithmetic structure. Timers repeat on cycles. Fractions need simplification. Hashing and combinatorics work under large moduli because exact integers explode in size. Scheduling problems ask when periodic events line up again. All of those situations are quietly about greatest common divisors, least common multiples, and modular arithmetic. These are not “math contest extras.” They are practical tools for keeping numeric programs correct, fast, and safe from overflow.
The unifying theme is reduction. GCD reduces two numbers to their shared building block. LCM reduces two repeating cycles to their first reunion. Mod arithmetic reduces huge intermediate values into a fixed range while preserving the parts of the computation you actually care about. Fast exponentiation reduces a long multiplication chain into repeated squaring. Once you see each technique as a way to keep only the essential information, the formulas stop feeling disconnected.
The Euclidean Algorithm for GCD
The greatest common divisor of a and b is the largest positive integer that divides both. The key observation behind Euclid’s algorithm is that gcd(a, b) = gcd(b, a mod b). Why? Because any number that divides both a and b also divides a - q·b for any integer q. In particular, it divides the remainder after removing as many full copies of b from a as possible. The common divisors do not change when you replace the larger number with the remainder.
That observation gives an iterative algorithm. Repeatedly replace (a, b) with (b, a mod b) until b becomes zero. At that point, a is the gcd. Every step shrinks the second number, so the process finishes quickly. More importantly, it is explainable: you are not guessing divisors one by one. You are preserving the set of common divisors while making the numbers smaller and smaller.
gcd(252, 198)
252 mod 198 = 54 -> gcd(198, 54)
198 mod 54 = 36 -> gcd(54, 36)
54 mod 36 = 18 -> gcd(36, 18)
36 mod 18 = 0 -> gcd(18, 0)
answer = 18Each transformation keeps the same common divisors but makes the pair easier to handle. When the remainder hits zero, the last non-zero value is the greatest common divisor.
If one input is zero, the gcd is the absolute value of the other input. The Euclidean loop handles this naturally as long as you define the base case clearly.
LCM and Cycle Alignment
The least common multiple is the smallest positive number divisible by both inputs. It answers “when do these cycles meet again?” If one job runs every 6 minutes and another every 8 minutes, they align every lcm(6, 8) = 24 minutes. The clean relationship is a × b = gcd(a, b) × lcm(a, b). Intuitively, the raw product counts shared prime factors twice, and the gcd measures exactly how much overlap should be divided out.
That leads to the standard formula lcm(a, b) = a / gcd(a, b) × b. The order matters in code. Dividing first avoids unnecessary overflow because a/gcd(a,b) is smaller than a, while still producing the same mathematical result. This is a small but important engineering habit: identical formulas on paper can have very different safety properties on a machine.
You can also read GCD and LCM through prime factors. The gcd keeps the overlapping prime powers that both numbers share, while the lcm keeps the highest power needed from either number. That viewpoint is slower to compute directly for large arbitrary inputs, which is why Euclid wins algorithmically, but it is a powerful sanity check. If two numbers share no prime factors, their gcd is 1 and their lcm is simply the product. If they share many factors, the gcd grows and the lcm shrinks relative to the raw product.
Modular Arithmetic as Controlled Forgetting
Working modulo m means you only care about remainders from 0 to m-1. This is useful whenever exact values grow far beyond what a fixed-width integer can hold. The reason modular arithmetic is safe is that addition and multiplication respect remainders: (a + b) mod m equals ((a mod m) + (b mod m)) mod m, and the same is true for multiplication. So you are allowed to reduce intermediate values early without changing the final remainder.
That “reduce early” rule is not just a math nicety. It is how you prevent overflow in practice. Suppose you are multiplying many terms under 1,000,000,007. If you wait until the very end to take the modulus, the intermediate product may far exceed 64-bit capacity. If you reduce after each multiplication, every stored value stays bounded. You are deliberately forgetting information that cannot affect the final answer, which is exactly what a modulus is meant to do.
Taking % mod at the end does not rescue an intermediate multiplication that already overflowed your integer type. Reduce during the computation, not after the damage is done.
Fast Power by Binary Exponentiation
Exponentiation is repeated multiplication, so the naive algorithm for a^b uses b multiplications. Binary exponentiation cuts that dramatically by reading the exponent in binary. If the current exponent bit is 1, multiply the answer by the current base. Then square the base and shift the exponent right. This works because every exponent can be decomposed into powers of two. You are effectively deciding which squared powers of the base belong in the final product.
Take 3^13 mod 17. The exponent 13 is 1101 in binary, which means 13 = 8 + 4 + 1. Start with answer = 1 and base = 3. The low bit is 1, so answer becomes 3. Square the base to 9 and shift the exponent to 6. The next bit is 0, so skip multiplying the answer. Square the base to 13 mod 17 and shift to 3. The next bit is 1, so answer becomes 3·13 mod 17 = 5. Square the base to 16 and shift to 1. The final bit is 1, so answer becomes 5·16 mod 17 = 12. That is the result, reached in logarithmic time.
| Task | Naive method | Efficient method | Complexity |
|---|---|---|---|
| GCD | Test every divisor down from min(a,b) | Euclidean algorithm | O(log min(a,b)) |
| LCM | Scan multiples until a common one appears | a/gcd(a,b) * b | O(log min(a,b)) after gcd |
| a^b mod m | Multiply a by itself b times | Binary exponentiation | O(log b) |
Go Implementation
The following Go functions are intentionally small and composable. They solve the individual subproblems, but they also model the habit of writing numeric helpers that you can reuse in many interview settings.
That reusability matters because many interview problems mix these tools. One task may need gcd to normalize a ratio, lcm to reason about repeating events, and modPow to keep a count bounded. Treating them as a connected toolkit is more useful than memorizing each formula in isolation.
Practice Problems
Quiz
Why does gcd(a, b) equal gcd(b, a mod b)?
Summary
- Euclid’s algorithm preserves common divisors while shrinking the numbers quickly.
- LCM answers cycle-alignment questions and is computed from GCD without scanning multiples.
- Modular arithmetic lets you reduce intermediate values safely because addition and multiplication respect remainders.
- Binary exponentiation turns repeated multiplication into a logarithmic process by reading the exponent in binary.
- A mathematically correct formula can still be unsafe in code if it overflows before you reduce it.
Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.