Modular Arithmetic

Learning Objectives

Modular arithmetic is the algebra of remainders. It is one of the smallest pieces of mathematics that pays the largest dividends in computing: hashing, cryptography, pseudo-random generators, error-correcting codes, circular buffers, parsers for time and dates, and an entire branch of competitive programming all live inside the world of $a \bmod n$. By the end of this section you will be able to:

1. State and use the congruence relation $a \equiv b \pmod{n}$ and reason about equivalence classes.
2. Manipulate modular expressions algebraically, knowing exactly when addition, subtraction, multiplication, and division are and are not safe.
3. Compute $a^b \bmod n$ in $O(\log b)$ time by repeated squaring, in both Python and TypeScript with BigInt.
4. Find modular inverses via the extended Euclidean algorithm and via Fermat's little theorem when $n$ is prime.
5. Recognize when modular arithmetic is the right tool, from hash tables and Rabin–Karp to RSA and circular buffers.
6. Avoid the classical landmines: negative numbers, signed-vs-unsigned overflow, non-prime moduli, and bad hash-table sizes.

Why this matters: almost every fast algorithm that touches integers eventually reduces them $\bmod n$. The hash table you use a thousand times a day is built on it. The HTTPS handshake that protects your bank login is built on it. Once modular arithmetic feels natural, large stretches of algorithms stop looking magical.

Definition: Congruence Modulo n

Fix an integer $n \geq 1$, called the modulus. Two integers $a$ and $b$ are congruent modulo $n$, written

$a \equiv b \pmod{n}$,

if $n$ divides their difference: $n \mid (a - b)$. Equivalently, they leave the same remainder when divided by $n$. So $17 \equiv 5 \pmod{12}$ because both leave remainder $5$ after division by $12$, and $12$ divides $17 - 5 = 12$.

Equivalence classes

Congruence is an equivalence relation: reflexive, symmetric, and transitive. So it carves the integers into $n$ disjoint equivalence classes, often written $[0], [1], \ldots, [n-1]$. The set of these classes, with the inherited addition and multiplication, is the ring $\mathbb{Z}/n\mathbb{Z}$. From the algorithm designer's point of view, $\mathbb{Z}/n\mathbb{Z}$ is just "the integers $\{0, 1, \ldots, n-1\}$ with arithmetic that wraps around at $n$."

Clock Arithmetic: The Pictorial Definition

A 12-hour clock is the canonical picture of arithmetic modulo $12$. If it is currently 7 o'clock and you wait 8 hours, the hour hand does not point to 15—it points to 3, because 15 mod 12 = 3. The clock automatically reduces every result back into $\{0, 1, \ldots, 11\}$. In symbols:

$7 + 8 \equiv 3 \pmod{12}$.

Three observations are worth memorizing because every other identity will follow from them:

• The clock has exactly $n$ positions, labeled $0, 1, \ldots, n-1$. There is no "12" on a mod-12 clock; the position you would call 12 is the same physical position as 0.
• Walking forward by $k$ steps and walking backward by $n - k$ steps land you in the same place. Negation is a wrap-around.
• Multiplication is repeated addition, so it also wraps—but with a twist we will examine: not every nonzero number on the clock has a multiplicative inverse.

Interactive: The Modular Wheel

Drag the modulus slider to change $n$, pick an operation (add $k$, multiply by $k$, or one binary-expansion step of squaring), and click Step to watch the pointer hop around the wheel. The history pane shows the residue stream, exactly what an algorithm sees.

The Algebra of Congruences

The reason modular arithmetic is so useful in algorithms is that addition, subtraction, and multiplication respect congruence. If $a \equiv a' \pmod n$ and $b \equiv b' \pmod n$, then

• $a + b \equiv a' + b' \pmod n$,
• $a - b \equiv a' - b' \pmod n$,
• $a \cdot b \equiv a' \cdot b' \pmod n$.

The practical corollary is the rule that lets you keep numbers small at every step of a computation:

$(a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n$,

$(a \cdot b) \bmod n = ((a \bmod n) \cdot (b \bmod n)) \bmod n$.

This is why a sum like $(123456 \cdot 987654 + 314159) \bmod 1000000007$ can be computed without ever forming a number larger than about $10^{18}$: reduce after every multiplication.

Why division is special

The same convenience does not hold for division. From $6 \equiv 0 \pmod 6$ we cannot divide both sides by 2 to conclude $3 \equiv 0 \pmod 6$—that statement is false. Division in $\mathbb{Z}/n\mathbb{Z}$ requires a modular inverse, which only exists when $\gcd(a, n) = 1$. We will return to this in a few sections.

A clean proof sketch

Why does multiplication respect congruence? If $a = a' + sn$ and $b = b' + tn$, then

$a b = (a' + sn)(b' + tn) = a' b' + n(a' t + b' s + s t n)$.

The second term is a multiple of $n$, so $ab \equiv a' b' \pmod n$. The proofs for addition and subtraction are identical and shorter.

Negative Numbers and the C/Python Divide

Mathematically, the canonical residue of $a$ mod $n$ is the unique integer in $\{0, 1, \ldots, n-1\}$. Real programming languages do not all agree on this convention.

Python and Mathematica use floor division: $a = n \lfloor a / n \rfloor + (a \bmod n)$ with the remainder always nonnegative. C and friends use truncation toward zero: $a = n \cdot \mathrm{trunc}(a / n) + (a \bmod n)$ with the remainder taking the sign of $a$.

1r = ((a % n) + n) % n;   // works in C, C++, Java, Go, Rust, JS, TS

Modular Exponentiation by Repeated Squaring

Many algorithms—Rabin–Karp, Miller–Rabin primality, RSA, Diffie–Hellman, polynomial hashing, modular combinatorics—need to compute $a^b \bmod n$ for large $b$. Computing $a^b$ naively, then reducing, is hopeless: with $a = 3$ and $b = 10^9$ the intermediate number has about half a billion digits.

The fix is the identity

$a^b = \begin{cases} 1 & \text{if } b = 0, \\ (a^{b/2})^2 & \text{if } b \text{ is even}, \\ a \cdot (a^{(b-1)/2})^2 & \text{if } b \text{ is odd}. \end{cases}$

Each level of recursion halves $b$, so the depth is $\lfloor \log_2 b \rfloor + 1$. The iterative form walks the binary representation of $b$ from least to most significant bit, maintaining two registers: $\text{base} = a^{2^i} \bmod n$ and a running $\text{result}$. Wherever the bit is $1$, multiply the result by the current base; in either case, square the base.

Python implementation

power_mod(7, 100, 1) == 0

If a = 1234567 and n = 13, base becomes 1234567 % 13 = 11.

If b = 13 (binary 1101), the bits encountered are 1, 0, 1, 1.

After bit 0 with base = 7, result = 1 * 7 % n = 7.

If base was 7 mod 13, next base = 49 mod 13 = 10.

1def power_mod(a: int, b: int, n: int) -> int:
2    """Return a**b mod n in O(log b) multiplications.
3
4    Works for any non-negative b and any n >= 1.
5    """
6    if n == 1:
7        return 0                       # everything is 0 mod 1
8
9    result = 1
10    base = a % n                       # canonicalize the base
11    while b > 0:
12        if b & 1:                      # current low bit is 1?
13            result = (result * base) % n
14        base = (base * base) % n       # square for the next bit
15        b >>= 1                        # shift to next bit of exponent
16
17    return result

TypeScript implementation with BigInt

In any fixed-precision language, the product $\text{result} \cdot \text{base}$ can overflow even when both operands are below $n$. For cryptographic-size moduli the only sane option is an arbitrary-precision integer type. JavaScript and TypeScript ship one: bigint.

((-7n) % 3n + 3n) % 3n === 2n.

1export function powerMod(a: bigint, b: bigint, n: bigint): bigint {
2  if (n === 1n) return 0n;
3  if (b < 0n) {
4    throw new RangeError("powerMod: negative exponent requires a modular inverse");
5  }
6
7  let result = 1n;
8  let base = ((a % n) + n) % n;        // canonical residue, even if a < 0
9  let exp = b;
10  while (exp > 0n) {
11    if ((exp & 1n) === 1n) {
12      result = (result * base) % n;
13    }
14    base = (base * base) % n;
15    exp >>= 1n;
16  }
17  return result;
18}

Interactive: Watching Repeated Squaring

The visualizer below traces every iteration of power_mod(a, b, n). The binary expansion of $b$ is highlighted, and each row shows whether the current bit triggered a multiplication and what the running result becomes. The number of steps is exactly the number of bits in $b$: that is the $O(\log b)$ guarantee, made physical.

Modular Inverses

The modular inverse of $a$ modulo $n$ is the unique residue $a^{-1} \in \{0, \ldots, n-1\}$ satisfying

$a \cdot a^{-1} \equiv 1 \pmod n$.

It exists if and only if $\gcd(a, n) = 1$. The proof is constructive: Bézout's identity guarantees integers $x, y$ with $a x + n y = 1$, and then $x \bmod n$ is the inverse. The tool that finds $x, y$ is the extended Euclidean algorithm.

Method 1: Extended Euclidean

ext_gcd(252, 105) -> ext_gcd(105, 42) -> ext_gcd(42, 21) -> ext_gcd(21, 0).

mod_inverse(6, 9) raises because gcd(6, 9) = 3.

mod_inverse(3, 11) returns 4, since 3 * 4 = 12 ≡ 1 (mod 11).

1def ext_gcd(a: int, b: int) -> tuple[int, int, int]:
2    """Return (g, x, y) with a*x + b*y == g == gcd(a, b)."""
3    if b == 0:
4        return a, 1, 0
5    g, x1, y1 = ext_gcd(b, a % b)
6    return g, y1, x1 - (a // b) * y1
7
8
9def mod_inverse(a: int, n: int) -> int:
10    """Return a^{-1} mod n; raises if gcd(a, n) != 1."""
11    g, x, _ = ext_gcd(a % n, n)
12    if g != 1:
13        raise ValueError(f"inverse does not exist: gcd({a}, {n}) = {g}")
14    return x % n

Method 2: Fermat's little theorem (when n is prime)

If $p$ is prime and $\gcd(a, p) = 1$, then $a^{p-1} \equiv 1 \pmod p$, so multiplying both sides by $a^{-1}$ gives the closed form

$a^{-1} \equiv a^{p-2} \pmod p$.

Combined with power_mod, this is a one-liner that runs in $O(\log p)$ time. Competitive programmers reach for it constantly because $p = 10^9 + 7$ is prime.

1def mod_inverse_prime(a: int, p: int) -> int:
2    """Inverse of a mod p when p is prime and gcd(a, p) = 1."""
3    return power_mod(a, p - 2, p)

Fermat's Little Theorem

Stated cleanly: for any prime $p$ and any integer $a$ with $\gcd(a, p) = 1$,

$a^{p-1} \equiv 1 \pmod p$.

Equivalently, for every integer $a$ (no coprimality needed), $a^p \equiv a \pmod p$. The proof, due to Euler, observes that the map $x \mapsto a x \pmod p$ permutes $\{1, 2, \ldots, p-1\}$, so the product of those residues equals the product of their $a$-multiples. Cancel the common product, and the identity drops out.

Why algorithms care

• Cheap inverses mod a prime, as we just saw.
• Probabilistic primality testing. Pick a random $a$; if $a^{n-1} \not\equiv 1 \pmod n$, then $n$ is composite. The contrapositive is the basis of the Fermat test, refined into the Miller–Rabin test you will meet in Chapter 37.
• RSA correctness. The key derivation in RSA uses Fermat (and its generalization, Euler's theorem) to guarantee that decryption inverts encryption.

A Glimpse of the Chinese Remainder Theorem

Suppose moduli $n_1, n_2, \ldots, n_k$ are pairwise coprime, with product $N = n_1 n_2 \cdots n_k$. The Chinese Remainder Theorem says the system of congruences

$x \equiv r_1 \pmod{n_1}, \quad x \equiv r_2 \pmod{n_2}, \quad \ldots, \quad x \equiv r_k \pmod{n_k}$

has a unique solution modulo $N$, and there is an explicit formula for it. Conceptually, residues mod $N$ can be split into independent residues mod each $n_i$ and reassembled. Algorithmically this means: a single problem on a huge modulus can be replaced by several smaller, independent problems—massive speed wins for big-integer multiplication, RSA decryption (via $p$ and $q$ separately), and signal processing.

We will treat CRT properly in Chapter 37 once we have its full algorithmic context. For now, just remember: it is the structural reason that composite moduli factor cleanly into their prime parts.

Why Algorithms Care About Modular Arithmetic

Modular arithmetic is one of the most leveraged primitives in computing. A non-exhaustive tour:

Worked example: Rabin–Karp polynomial hashing

To find a pattern $P$ of length $m$ inside a text $T$ of length $n$, define a hash for any window $T[i..i+m-1]$ by treating its characters as digits in base $B$ mod a large prime $p$:

$H_i = \Big( \sum_{j=0}^{m-1} T[i+j] \cdot B^{m-1-j} \Big) \bmod p$.

Sliding the window by one position is then an $O(1)$ operation:

$H_{i+1} = \big( (H_i - T[i] \cdot B^{m-1}) \cdot B + T[i+m] \big) \bmod p$.

Modular arithmetic keeps every intermediate small enough to fit in a 64-bit word; without it, the hash itself would have $m \log B$ bits and updating it would be linear, not constant, in $m$.

Edge Cases and Pitfalls

1. Negative numbers in C-family languages

We have already covered the canonicalization idiom. The bug is so common that some teams ban raw % in favor of a positiveMod wrapper.

2. Hashing with $m = 2^k$

It is tempting to take the modulus to be a power of two, because $x \bmod 2^k$ is a bitmask. But this throws away every bit of $x$ above position $k$. If the high bits of your hash function carry the entropy (very common), the table degenerates and collisions explode. Use a prime modulus for hash tables, or hash with a strong mixing function before masking.

3. Inverse does not exist

Calling mod_inverse(6, 9) is a bug, not a number. Always check $\gcd(a, n) = 1$, or design the modulus so it is prime.

4. Off-by-one in circular indexing

For a buffer of capacity $n$, the next index after $i$ is $(i + 1) \bmod n$ and the previous is $(i + n - 1) \bmod n$. Writing $(i - 1) \bmod n$ in C will return $-1$ for $i = 0$—a memory bug, not a wrap-around.

5. Overflow in fixed-width languages

With 64-bit integers, $(a \cdot b) \bmod n$ overflows whenever $n \gtrsim 2^{32}$. Use 128-bit intermediates (__int128 in C++, BigInteger in Java) or Montgomery/Barrett reduction.

Summary

Modular arithmetic is the connective tissue between integer algebra and the bounded-precision world of computer arithmetic. Once the four habits—reduce early, canonicalize negatives, use repeated squaring, watch for non-existent inverses—become reflex, the rest of cryptography, hashing, and number-theoretic algorithms reads like applied common sense.

Exercises

Computation

1. Compute by hand: $(-17) \bmod 5$ in both Python and C semantics.
2. Use repeated squaring on paper to compute $3^{13} \bmod 7$. Show the binary expansion of $13$ and the running product at each step.
3. Find $7^{-1} \bmod 11$ two different ways: extended Euclidean, and Fermat's little theorem.
4. Show that $6$ has no inverse modulo $9$. What about modulo $11$?

Implementation

1. Implement power_mod recursively (split on parity of $b$) and verify it agrees with the iterative version on 1000 random inputs.
2. Write a Rabin–Karp substring search using rolling polynomial hashing modulo $p = 10^9 + 7$. Verify the result on a known case before trusting it; collisions are real.
3. Build a circular buffer of capacity 8 using $(i + 1) \bmod 8$ for advance and $(i + 7) \bmod 8$ for retreat. Stress-test it with random push/pop sequences.

Conceptual

1. Prove that if $a \equiv b \pmod n$ and $c \equiv d \pmod n$, then $a c \equiv b d \pmod n$. Where in the proof do you use $n \mid (a - b)$?
2. Suppose $m$ is the size of a hash table and $h$ is a hash function. Argue that if $m$ shares a large factor with the typical period of $h$, you should expect clustering. (This is the practical reason for prime moduli.)
3. Why does Fermat's little theorem fail for composite $n$? Find an $a$ with $a^{n-1} \not\equiv 1 \pmod{n}$ when $n = 15$.

With logarithms, summations, induction, probability, and now modular arithmetic in hand, you possess the entire mathematical kit a working algorithm designer needs day-to-day. The next chapter turns this kit on its first major target: Recursion Mastery.