Modular Arithmetic

Modular arithmetic keeps only the remainder after division by a modulus.

Algorithm problems use it to keep large numbers manageable and to reason about cycles.

Core Idea

If two numbers have the same remainder modulo m, they are equivalent for many remainder-based calculations. Addition and multiplication can be reduced modulo m at each step without changing the final remainder.

This is why large counting answers are often returned modulo a number such as 1_000_000_007.

Python Example

MOD = 1_000_000_007
 
answer = 0
for value in [10, 20, 30]:
    answer = (answer + value) % MOD

The value stays within the modulus range after each update.

Common Confusions

Modulo does not preserve ordinary division. Modular division requires an inverse, and that inverse may not exist.

Python’s % returns a non-negative remainder when the modulus is positive, even for negative inputs.

When To Use It

Use modular arithmetic for large counts, repeated multiplication, cyclic behavior, hash formulas, and problems that explicitly ask for a result modulo some value.