Arithmetic that wraps around
Modular arithmetic treats numbers by their remainder after dividing by a fixed modulus m. Two numbers are congruent modulo m if they leave the same remainder. Like a clock that resets after twelve, values stay within a bounded range.
The rules that make it useful
The remainder operation distributes over addition, subtraction, and multiplication:
- The remainder of a sum equals the sum of the remainders, reduced again.
- The same holds for products.
- This means you can reduce early and often without changing the final remainder.
Reducing at each step keeps intermediate values small, which prevents overflow and keeps arithmetic fast.
Division is special
Division does not work directly. To divide by a number you multiply by its modular inverse, which exists only when that number is coprime to the modulus. When the modulus is prime, every nonzero value has an inverse, which is why prime moduli are popular in cryptography and hashing.
Key idea
Modular arithmetic keeps only remainders modulo m; addition and multiplication commute with reduction, so reduce often to stay small, while division needs a modular inverse that exists when the operand is coprime to m.