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.

Usage Contract

Modulo calculations expect a positive modulus m.

Addition and multiplication can be reduced modulo m during computation. Division is different and requires a modular inverse, which may not exist.

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.

Addition and Multiplication

Modulo can be applied during computation:

(a + b) % MOD == ((a % MOD) + (b % MOD)) % MOD
(a * b) % MOD == ((a % MOD) * (b % MOD)) % MOD

This lets algorithms avoid huge intermediate values while preserving the final remainder.

Cycles

Modulo also describes cycles. For example, (i + 1) % n moves to the next index in a circular array and wraps back to 0 after n - 1.

Modular Division

Division is special. To divide by x modulo m, the algorithm needs a modular inverse of x. That inverse exists only under certain conditions, such as x and m being coprime.

Step-by-Step Example

Suppose the answer is a large product:

result = 1
for value in values:
    result = (result * value) % MOD

Taking % MOD after each multiplication gives the same final remainder as multiplying everything first and taking % MOD at the end, but it keeps intermediate values small.

Complexity Role

Modulo usually does not change the number of algorithm steps. It changes the size of the numbers being carried through those steps and keeps the requested answer in the required range.

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.

Another common mistake is applying modulo only at the very end in languages with fixed-size integers. Python handles big integers, but many languages overflow first.

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.

Do not use modulo to hide an incorrect count. The recurrence or formula must be correct before taking remainders.

The Main Point

Modulo arithmetic preserves remainders under addition and multiplication, but division needs a valid inverse.