Modular arithmetic is a fundamental tool in coding interviews, especially when dealing with large numbers, constraints, and repetitive patterns. It allows you to work within a fixed range by wrapping values around a modulus, which helps prevent overflow and keeps computations efficient.

You will encounter it in problems involving remainders, cyclic patterns, hashing, and combinatorics. The rest of this chapter covers the core arithmetic properties, the modulus 10^9 + 7, fast exponentiation, and the modular inverse.

The modulo operation gives you the remainder when one integer is divided by another. When we write a % m (or a mod m), we are asking: "What is left over after dividing a by m?"

For example:

One way to picture this is as a clock face. If your modulus is 7, the positions 0 through 6 form a cycle, and counting forward past 6 wraps back to 0. So 10 mod 7 = 3: starting at 0 and counting 10 steps on a 7-position clock means going around the full cycle once (7 steps) and landing 3 steps in.

The power of modular arithmetic lies in its properties. These properties let you take the mod at every intermediate step of a computation, keeping numbers small, while still getting the correct final result.

Addition Property

Example: (15 + 23) % 7 = 38 % 7 = 3. Alternatively: (15 % 7 + 23 % 7) % 7 = (1 + 2) % 7 = 3. Same answer.

Multiplication Property

Example: (15 · 23) % 7 = 345 % 7 = 2. Alternatively: ((15 % 7) · (23 % 7)) % 7 = (1 · 2) % 7 = 2. Same answer.

Subtraction Property (Handling Negatives)

The extra + m is critical. In many programming languages (Java, C++, C#, JavaScript), the % operator can return negative values when the left operand is negative. For example, -3 % 7 returns -3 in Java, not 4. Adding m before taking mod again ensures the result is always non-negative.

Example: Compute (5 - 8) % 7. The mathematically correct remainder is 4, since -3 = -1 · 7 + 4. But in Java and C++, the expression -3 % 7 evaluates to -3. The safe formula gives ((5 - 8) % 7 + 7) % 7 = (-3 + 7) % 7 = 4.

Division Property (No Direct Division!)

Here is the one operation that does NOT work the way you might expect:

You cannot simply divide and take mod. Instead, you need the modular multiplicative inverse, which we cover shortly. Division in modular arithmetic is performed by multiplying by the inverse.

You will see the number 1000000007 (10^9 + 7) in countless problems. This is not arbitrary. It was chosen for very specific reasons:

Computing a^n mod m is one of the most fundamental operations. The naive approach of multiplying a by itself n times is O(n), which is far too slow when n can be 10^9 or larger.

Binary exponentiation (also called fast power or exponentiation by squaring) computes a^n mod m in O(log n) time. The key insight is based on the following recurrence:

Instead of n multiplications, we only need log(n) multiplications because we halve the exponent at each step.

The iterative version processes the binary representation of the exponent from least significant bit to most significant bit. If the current bit is 1, multiply result by the current base. Either way, square the base and shift the exponent right. Here is the trace for pow(2, 10, mod), where 10 = 1010 in binary:

Four iterations replace what would be ten multiplications in the naive approach. For an exponent like 10^18, this drops 10^18 operations to about 60.

The modular inverse of a modulo m is a number x such that:

We write this as a^(-1) mod m. The inverse exists if and only if gcd(a, m) = 1. The reason follows from Bezout's identity: when gcd(a, m) = 1, there exist integers x, y with a · x + m · y = 1. Reduce both sides modulo m: the m · y term vanishes and we get a · x ≡ 1 (mod m), so x mod m is the inverse. Conversely, if gcd(a, m) = d > 1, then every multiple of a is also a multiple of d, so a · x can never equal 1 modulo m. For composite m, the Extended Euclidean algorithm is the standard way to get the inverse.

Since 10^9 + 7 is prime, every number from 1 to 10^9 + 6 is coprime to it and has an inverse.

Why do we need this? Whenever you need to compute (a / b) % m, you instead compute (a * b^(-1)) % m, where b^(-1) is the modular inverse of b.

Fermat's Little Theorem

When m is prime, Fermat's Little Theorem states:

a^(m-1) ≡ 1 (mod m) for any a not divisible by m

Multiply both sides by a^(-1):

a^(m-2) ≡ a^(-1) (mod m)

So the modular inverse is just a^(m-2) mod m, computable in O(log m) with the binary exponentiation function above. No new algorithm needed.

Example: To compute (6 / 3) % 7, we need the inverse of 3 mod 7.

Below are complete implementations of modular exponentiation and modular inverse:

The iterative version is preferred in interviews and competitive programming because it avoids stack overflow for very large exponents and uses constant space.

For modular inverse, since we compute a^(m-2) mod m and m = 10^9 + 7, the time complexity is O(log(10^9 + 7)) which is roughly O(30), effectively constant.