If it is 10 o'clock now and I add 5 hours, the clock shows 3, not 15. Every day we use an arithmetic in which numbers "wrap around". Modular arithmetic formalises this idea, and it is everywhere in computing: hash tables, circular buffers, pseudorandom number generators, calendars, check digits and cryptography.
Division with remainder
Given two integers a and n with n > 0, there are unique integers q (quotient) and r (remainder) such that
a = q · n + r, with 0 ≤ r < n
The remainder is written a mod n. For example 17 mod 5 = 2, because 17 = 3 · 5 + 2. And −7 mod 5 = 3, because −7 = (−2) · 5 + 3.
Congruences
Two integers a and b are congruent modulo n if n divides their difference:
a ≡ b (mod n) ⟺ n | (a − b)
Equivalently, a and b leave the same remainder when divided by n. So 17 ≡ 2 ≡ −3 ≡ 32 (mod 5).
Congruence modulo n is an equivalence relation, and it splits the integers into n classes: those of remainders 0, 1, …, n − 1. The set of these classes is written ℤₙ.
Operations respect congruences
The property that makes all this useful is that addition, subtraction and multiplication are compatible with congruences: if a ≡ a′ and b ≡ b′ (mod n), then
- a + b ≡ a′ + b′ (mod n)
- a − b ≡ a′ − b′ (mod n)
- a · b ≡ a′ · b′ (mod n)
In practice you can reduce modulo n at any point in a calculation without changing the final result. That is what lets you work with small numbers even when the intermediate numbers would be huge.
Example: the last digit of a power
What is the last digit of 7²⁰²⁶? The last digit is the remainder modulo 10. The powers of 7 modulo 10 are 7, 9, 3, 1, 7, 9, 3, 1, … with period 4. Since 2026 = 4 · 506 + 2, we have 7²⁰²⁶ ≡ 7² ≡ 9 (mod 10). The last digit is 9.
Beware of division
Division is not compatible in general: 2 · 3 ≡ 2 · 8 (mod 10), because 6 and 16 have the same last digit, but 3 is not congruent to 8 modulo 10. You cannot "cancel" the 2.
You can divide by a modulo n only when a has an inverse, a number b with a · b ≡ 1 (mod n). This happens exactly when a and n share no factors. If n is prime, every number that is not a multiple of n is invertible, and ℤₙ behaves like a set in which all four operations are possible.
The modulo operator in programming languages
There is a trap here. With negative numbers, different languages give different results:
| Expression | Python | C, Java, JavaScript |
|---|---|---|
| 7 % 3 | 1 | 1 |
| −7 % 3 | 2 | −1 |
| 7 % −3 | −2 | 1 |
Python returns a remainder with the same sign as the divisor, consistent with the mathematical definition when n > 0. C, Java and JavaScript truncate the quotient towards zero, and the remainder takes the sign of the dividend.
This causes real bugs. An index into a circular buffer computed as (i - 1) % n in C or Java becomes −1 when i = 0, and the array access fails. The safe form is:
int index = ((i - 1) % n + n) % n;
Modular powers
Computing aᵉ mod n with a very large e is a central operation in cryptography. You never compute aᵉ in full: you use exponentiation by repeated squaring, reducing modulo n at each step. In Python it is built in:
pow(7, 2026, 10) # 9
pow(3, 10**18, 1000003) # instant result
Fermat's little theorem
If p is prime and a is not a multiple of p, then
aᵖ⁻¹ ≡ 1 (mod p)
Example: with p = 7 and a = 3, we have 3⁶ = 729 = 104 · 7 + 1, so 3⁶ ≡ 1 (mod 7).
Two practical consequences:
- Reducing exponents: modulo a prime p, exponents can be reduced modulo p − 1. For example 3¹⁰⁰ mod 7: 100 mod 6 = 4, so 3¹⁰⁰ ≡ 3⁴ = 81 ≡ 4 (mod 7).
- Primality testing: if for some a you find aⁿ⁻¹ ≢ 1 (mod n), then n is certainly composite. The converse does not hold: there are composite numbers, called Carmichael numbers, that pass the test for every base a sharing no factors with n; the smallest is 561. The tests used in practice, such as Miller-Rabin, strengthen this idea.
In short
- a ≡ b (mod n) means that n divides a − b, that is, a and b leave the same remainder.
- Addition, subtraction and multiplication can be reduced modulo n at any point.
- Division is only possible by invertible numbers, those sharing no factors with n.
- With negatives, the % operator behaves differently across languages: watch out for circular indices.
- Fermat's little theorem lets you reduce exponents and rule out composite numbers.
