Foundations
Modular Arithmetic
Difficulty: Advanced
Open any production hash table, any block cipher, any RSA implementation, or any competitive programming problem that ends in "output the answer modulo 10^9 + 7", and you will find the same machinery underneath: modular arithmetic, the...
Modular Arithmetic
Open any production hash table, any block cipher, any RSA implementation, or any competitive programming problem that ends in "output the answer modulo 10^9 + 7", and you will find the same machinery underneath: modular arithmetic, the math of working with remainders rather than full integers. It is the bridge between number theory and a huge swath of real algorithms.
This lesson develops that machinery from first principles. You will revisit the mod operation precisely (including its relationship to division and remainders), then prove and use the addition, subtraction, and multiplication rules that let you take mod at every step of a long calculation without changing the answer. From there you will implement fast modular exponentiation in O(log n) time using binary exponentiation, compute modular inverses with Fermat's Little Theorem when the modulus is prime, and see exactly why hash tables, RSA, and contest problems rely on these tricks to avoid overflow and to invert multiplications.
This lesson builds on Number Theory Fundamentals, where you learned about primes, divisibility, gcd, and the Euclidean algorithm. Modular arithmetic uses all of those: primality lets you apply Fermat, gcd decides when an inverse exists, and divisibility underlies every congruence.
From here the only foundations topic remaining is Basic Proof Techniques, where you will learn the proof tools (induction, contradiction, contraposition) that make the kinds of arguments you have just been waving at fully rigorous.
Prerequisites:
Number Theory FundamentalsTopics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain the modulo operation and its relationship to division and remainders.
Apply the properties of modular arithmetic (addition, subtraction, multiplication) to simplify computations.
Implement modular exponentiation using fast exponentiation (binary exponentiation) in O(log n) time.
Compute modular inverses using Fermat's Little Theorem when the modulus is prime.
Identify when and why modular arithmetic is used in hash functions, cryptography, and competitive programming.
Solve problems that require computing large results modulo a prime.
Why This Matters
01
Hash functions use modular arithmetic to map keys into fixed-size buckets -- understanding mod properties helps you analyze collision behavior and design better hash schemes.
02
Cryptographic algorithms like RSA are built entirely on modular exponentiation and modular inverses -- these are the mathematical bedrock of internet security.
03
Competitive programming problems frequently require computing answers 'modulo 10^9 + 7' to avoid integer overflow -- you need to know how to correctly apply modular operations to additions, multiplications, and divisions.
04
Modular arithmetic provides elegant O(log n) algorithms for exponentiation and inverse computation, replacing brute-force approaches that would be computationally infeasible for large inputs.
Key Terms
6 terms you'll encounter in this lesson
Modulo Operation
The operation a mod m returns the remainder when a is divided by m. For example, 17 mod 5 = 2 because 17 = 3 x 5 + 2. Written as a % m in most programming languages.
Congruence
Two integers a and b are congruent modulo m (written a ≡ b (mod m)) if they have the same remainder when divided by m, or equivalently, if m divides (a - b). For example, 17 ≡ 2 (mod 5).
Modular Inverse
The modular inverse of a modulo m is an integer x such that (a * x) mod m = 1. It exists only when GCD(a, m) = 1. For example, the inverse of 3 mod 7 is 5 because 3 * 5 = 15 ≡ 1 (mod 7).
Fermat's Little Theorem
If p is prime and a is not divisible by p, then a^(p-1) ≡ 1 (mod p). This gives us the modular inverse: a^(-1) ≡ a^(p-2) (mod p).
Binary Exponentiation
An algorithm to compute a^n mod m in O(log n) time by repeatedly squaring the base and using the binary representation of the exponent. Also called fast exponentiation or exponentiation by squaring.
Modular Multiplicative Inverse
For integer a and prime modulus p, the value a^(p-2) mod p is the multiplicative inverse of a modulo p. It allows modular 'division': (b / a) mod p = (b * a^(p-2)) mod p.
Heads Up
Common misconceptions to watch out for
"(a - b) mod m is always positive"
In many languages (C, C++, Java), the % operator can return negative values when the dividend is negative. For example, (-3) % 5 = -3 in C. To ensure a positive result, use ((a - b) % m + m) % m.
"I can just divide under modular arithmetic like normal"
Division does not work directly with modular arithmetic. Instead of (a / b) mod m, you must compute a * b^(-1) mod m, where b^(-1) is the modular inverse of b. Division is replaced by multiplication with the inverse.
"Modular inverse always exists"
The modular inverse of a mod m exists only when GCD(a, m) = 1 (they are coprime). If m is prime, every non-zero a has an inverse. But if m is composite, some values of a have no inverse (e.g., 2 has no inverse mod 4).
"I can compute a^n mod m by first computing a^n then taking mod"
For large n, a^n can be astronomically large -- far exceeding what any integer type can hold. You must apply mod at every multiplication step to keep numbers manageable. Binary exponentiation does this automatically.