Modular Arithmetic

Wrap-around · Fast Power

1:00

How numbers wrap around like a clock, why reducing early keeps computations small, and how binary exponentiation computes a^b mod m in O(log b) steps.

By the end, you can

Compute a mod m and determine whether two numbers are congruent mod m.
Normalize a negative remainder into the canonical range 0…m−1.
Apply the reduce-early property to compute products mod m without overflow.
Determine whether a modular inverse exists and find it by brute force or Fermat's theorem.
Trace binary exponentiation step by step and explain why it runs in O(log b) time.
Trace the modpow loop (bit check, fold, square, shift) on a concrete example.
Identify the three main application areas where mod is indispensable: overflow avoidance, hashing, and cryptography.

Up next in Math, Memory & Files