Modular Arithmetic

Modular arithmetic is what happens when numbers live on a clock face instead of a number line. Add two hours past $11$ and you do not get $13$, you get $1$. That single twist, “wrap around at $n$,” is the foundation of every hash table key, every check-digit on an ISBN or credit card, every cyclic redundancy check (CRC) error-detection scheme inside Ethernet frames, every cryptographic key exchange. The remainder operation $a \bmod n$ is fast, deterministic, and folds an unbounded space of integers into a finite set of $n$ equivalence classes, which is exactly the data structure you want for indexing, signing, and verifying.

The definition: congruence

For a positive integer $n$, we say $a$ is congruent to $b$ modulo $n$, written $a \equiv b \pmod{n}$, when $n \mid (a - b)$. Equivalently, $a$ and $b$ leave the same remainder when divided by $n$. Example: $17 \equiv 2 \pmod{5}$ because $5 \mid (17 - 2) = 15$.

Congruence is an equivalence relation: reflexive ($a \equiv a$), symmetric ($a \equiv b \Rightarrow b \equiv a$), and transitive ($a \equiv b$ and $b \equiv c$ give $a \equiv c$). Equivalence relations carve the integers into classes; the $n$ classes for modulus $n$ are written $[0], [1], \ldots, [n-1]$ and collectively form the set $\mathbb{Z}/n\mathbb{Z}$.

Arithmetic respects congruence

If $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then $a + c \equiv b + d \pmod{n}$, $a - c \equiv b - d \pmod{n}$, $ac \equiv bd \pmod{n}$, and $a^k \equiv b^k \pmod{n}$ for any $k \geq 1$. This is what makes $\mathbb{Z}/n\mathbb{Z}$ a ring: addition and multiplication are well-defined on the equivalence classes. Division, however, is more delicate, we will get there.

(Set the modulus in the widget above and type a single integer; the hand sweeps to its representative class. Try increasing values of $n$ past the modulus and observe how the hand wraps around. To see addition wrap, compute $(7 + 5) \bmod 12$ and $(10 + 6) \bmod 12$ on paper, then enter the sums into the widget to confirm.)

Modular inverses and linear congruences

The linear congruence $ax \equiv b \pmod{n}$ asks for an $x$ such that $ax - b$ is a multiple of $n$. It has a solution if and only if $\gcd(a, n) \mid b$. The cleanest special case: $\gcd(a, n) = 1$. In that case $a$ has a unique modular inverse $a^{-1}$ mod $n$, and the solution is $x \equiv a^{-1} b \pmod{n}$. The inverse comes from Bezout: write $sa + tn = 1$; then $sa \equiv 1 \pmod{n}$, so $a^{-1} \equiv s \pmod{n}$.

Worked example. Solve $3x \equiv 5 \pmod{7}$. Since $\gcd(3, 7) = 1$, an inverse exists. Try small multiples: $3 \cdot 5 = 15 \equiv 1 \pmod{7}$, so $3^{-1} \equiv 5 \pmod{7}$. Then $x \equiv 5 \cdot 5 = 25 \equiv 4 \pmod{7}$. Check: $3 \cdot 4 = 12 \equiv 5 \pmod{7}$.

Pause and think: What is $(-1)^{100} \pmod{n}$ for any $n \geq 2$? Now, harder, what is $(-1)^{101} \pmod{n}$? The fact that congruence respects exponentiation is doing real work for you in both answers.

Try it

• Predict: what is $7^{100} \bmod 4$? (Hint: $7 \equiv 3 \equiv -1 \pmod{4}$.) Verify by reducing $7$ first, then exponentiating.
• Solve $5x \equiv 3 \pmod{11}$. Find $5^{-1} \bmod 11$ by trial, then multiply.
• Compute $2^{10} \bmod 7$ without ever computing $2^{10} = 1024$ directly. (Hint: $2^3 = 8 \equiv 1$; how does that help?)
• Determine for which $n \in {2, 3, 4, 5, 6}$ the element $4$ has a modular inverse. Justify each case using $\gcd(4, n)$.

A trap to watch for

Addition, subtraction, and multiplication all carry over from $\mathbb{Z}$ to $\mathbb{Z}/n\mathbb{Z}$ without surprises. Division does not. You cannot blindly cancel: $6 \equiv 0 \pmod{6}$ but if you divide both sides by $2$, you get $3 \equiv 0 \pmod{6}$, which is false. The right statement is: if $\gcd(c, n) = 1$, then $ca \equiv cb \pmod{n}$ implies $a \equiv b \pmod{n}$. Cancellation is safe exactly when the cancelled factor is coprime to the modulus. A related trap: students sometimes write $a \bmod n = a/n$, but $a \bmod n$ is the remainder, not the quotient.

What you now know

You can compute inside $\mathbb{Z}/n\mathbb{Z}$, find modular inverses when they exist, and solve linear congruences. The next section, Euler’s theorem, generalises Fermat’s little theorem ($a^{p-1} \equiv 1 \pmod{p}$) to any modulus, replacing “$p - 1$” with $\phi(n)$, the count of units in $\mathbb{Z}/n\mathbb{Z}$.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, §7.3.
• Hardy, G. H., Wright, E. M. (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press, ch. 5.
• Niven, I., Zuckerman, H. S., Montgomery, H. L. (1991). An Introduction to the Theory of Numbers (5th ed.). Wiley, ch. 2.
• Rosen, K. H. (2010). Elementary Number Theory (6th ed.). Pearson, ch. 4.
• Stinson, D. R., Paterson, M. B. (2018). Cryptography: Theory and Practice (4th ed.). CRC Press, ch. 5.