Modular Arithmetic

Modular arithmetic, sometimes called ‘clock arithmetic’, is a system of arithmetic for integers in which numbers wrap around after reaching a fixed value called the modulus. If you take 15 hours past midnight on a 12-hour clock, you don’t land at 15 o’clock — you land at 3 o’clock, because clocks wrap around every 12 hours. That’s modular arithmetic. Formalized by Gauss in Disquisitiones Arithmeticae (1801), it’s the language of cryptography, hash functions, digital signal processing, and much of computer science.

Definition

Two integers $ a $ and $ b $ are congruent modulo $ n $ (written $ a \equiv b \pmod{n} $) if their difference is divisible by $ n $. In symbols:

$$ a \equiv b \pmod{n} \iff n \mid (a – b) $$

Equivalently, $ a $ and $ b $ leave the same remainder when divided by $ n $. The number $ n $ is the modulus.

Examples. $ 17 \equiv 5 \pmod{12} $ because $ 17 – 5 = 12 $ is divisible by 12. $ 38 \equiv 3 \pmod{7} $ because $ 38 = 5 \cdot 7 + 3 $. $ -1 \equiv 11 \pmod{12} $ because $ -1 – 11 = -12 $ is divisible by 12.

Operations Mod n

Addition, subtraction, and multiplication all work normally modulo $ n $:

$ (a + b) \bmod n = ((a \bmod n) + (b \bmod n)) \bmod n $.
$ (a – b) \bmod n $ — same rule.
$ (a \cdot b) \bmod n = ((a \bmod n) \cdot (b \bmod n)) \bmod n $.
Division is trickier: you can only divide by $ b $ modulo $ n $ when $ \gcd(b, n) = 1 $, and division is done by finding the modular inverse of $ b $.

Worked Examples

Day-of-week calculation. Today is Wednesday. What day is it 100 days from now? Take $ 100 \bmod 7 = 2 $. Add 2 days to Wednesday: Friday.

Last digit. The last digit of $ 7^{100} $ is $ 7^{100} \bmod 10 $. Powers of 7 mod 10 cycle: $ 7, 9, 3, 1, 7, 9, 3, 1, \ldots $ with period 4. $ 100 \bmod 4 = 0 $, so $ 7^{100} \equiv 7^4 \equiv 1 \pmod{10} $. Last digit is 1.

Solving a congruence. Solve $ 3x \equiv 7 \pmod{11} $. The inverse of 3 mod 11 is 4 (because $ 3 \cdot 4 = 12 \equiv 1 \pmod{11} $). So $ x \equiv 4 \cdot 7 = 28 \equiv 6 \pmod{11} $.

Fermat’s Little Theorem

If $ p $ is prime and $ a $ is not divisible by $ p $:

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

Equivalently, $ a^p \equiv a \pmod{p} $ for all integers $ a $ (including those divisible by $ p $). This is a workhorse for computing very large powers modulo a prime and is the basis of many primality tests.

Example. Compute $ 2^{100} \bmod 13 $. By Fermat’s little theorem, $ 2^{12} \equiv 1 \pmod{13} $. And $ 100 = 8 \cdot 12 + 4 $, so $ 2^{100} = (2^{12})^8 \cdot 2^4 \equiv 1 \cdot 16 \equiv 3 \pmod{13} $.

Applications

RSA encryption. RSA computes ciphertext as message^e mod n, where n = pq is the product of two large primes and e is the public exponent. Decryption uses message^d mod n, where d is the private exponent. Everything happens in modular arithmetic.
Hash functions. Hash tables use h(key) mod table_size to map keys to bucket indices. Prime table sizes minimize clustering.
Check digits. ISBN-10 check digit uses arithmetic mod 11; credit card numbers (Luhn algorithm) use a mod 10 check.
Pseudo-random number generators. Linear congruential generators (LCGs) compute X_{n+1} = (a · X_n + c) mod m. Choice of a, c, m determines the quality of the output sequence.
Cyclic structures. Days of the week, hours, calendars, angles (mod 360°), musical pitches (mod 12) — anything that repeats periodically is naturally described with modular arithmetic.
Error-correcting codes. Reed-Solomon and CRC checksums operate in modular arithmetic (often over finite fields with prime modulus).

Frequently Asked Questions

What is modular arithmetic?

A system of arithmetic for integers in which numbers wrap around after reaching a fixed modulus n. Two numbers are ‘congruent mod n’ if they leave the same remainder when divided by n. The most familiar example is a clock: 14 o’clock is the same as 2 o’clock, because they’re congruent mod 12.

What does ‘a ≡ b mod n’ mean?

It means ‘a and b leave the same remainder when divided by n’, or equivalently, ‘a − b is divisible by n’. Example: 17 ≡ 5 (mod 12) because both 17 and 5 leave remainder 5 when divided by 12, and 17 − 5 = 12 is divisible by 12.

Can you divide in modular arithmetic?

Not always. You can divide by b mod n only if b and n are coprime (gcd(b, n) = 1). When they are, division by b is performed by multiplying by the modular inverse of b — the number b⁻¹ such that b · b⁻¹ ≡ 1 (mod n). The extended Euclidean algorithm finds the inverse efficiently.

What is Fermat’s Little Theorem?

If p is prime and a is not divisible by p, then a^(p−1) ≡ 1 (mod p). This is a fast way to compute large powers modulo a prime, and it’s the basis of several primality tests, including the Miller-Rabin probabilistic test. It also underlies parts of RSA cryptography.

How is modular arithmetic used in cryptography?

It’s the entire mathematical setting of RSA and many other cryptosystems. RSA computes ciphertext = message^e mod n, where n is the product of two large primes. Without modular arithmetic, encryption and decryption — done via modular exponentiation — wouldn’t make sense or be feasible at scale.

Who invented modular arithmetic?

Carl Friedrich Gauss formalized it in ‘Disquisitiones Arithmeticae’ (1801), introducing the ≡ notation and laying down the basic theorems. The underlying ideas are much older — Chinese mathematicians had results equivalent to the Chinese Remainder Theorem by the 3rd century CE, and Euclid’s algorithm goes back to about 300 BCE.