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. It also plays a key role in optimizing solutions where direct computation would be too large or too slow.

In this chapter, we will build a clear intuition for modular arithmetic, understand its core properties, and learn how to apply it in common interview scenarios.

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 visualize this is as a clock. If your modulus is 7, then the numbers 0 through 6 form a cycle. After 6, you wrap back around to 0. The number 10 mod 7 is 3, because starting from 0 and counting 10 steps on a 7-hour clock lands you at 3.

In this diagram, 3 is highlighted because 10 mod 7 = 3. After wrapping once through the full cycle (7 steps) you land at position 3 with the remaining 3 steps.

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: (5 - 12) % 7 = -7 % 7 = 0. Using the safe formula: ((5 % 7) - (12 % 7) + 7) % 7 = (5 - 5 + 7) % 7 = 7 % 7 = 0.

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 will 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 a bit is 1, we multiply the result by the current base. At each step, we square the base.

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

We write this as a^(-1) mod m. It exists if and only if a and m are coprime (their GCD is 1). Since 10^9 + 7 is prime, every number from 1 to 10^9 + 6 has an inverse modulo 10^9 + 7.

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 (which it is for 10^9 + 7), Fermat's Little Theorem gives us an elegant formula:

This means we can compute the modular inverse by raising a to the power m - 2 using our binary exponentiation function. No new algorithm needed.

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

Let us trace through the iterative binary exponentiation algorithm step by step to compute 2^10 mod (10^9 + 7).

First, the binary representation of 10 is 1010.

The algorithm maintains two variables: result (starts at 1) and base (starts at a = 2). We scan the bits of the exponent from right to left.

Let us verify: 2^10 = 1024. Since 1024 < 10^9 + 7, the mod does not change the result. The answer is 1024.

The beauty here is that we only performed 4 iterations (log2(10) ≈ 3.32, rounded up to 4), compared to 10 multiplications with the naive approach. For an exponent like 10^18, the naive approach would need 10^18 operations (impossible), while binary exponentiation needs only about 60 iterations.

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.

1. Not handling negative results from the mod operator

This is the single most common bug. In Java, C++, C#, and JavaScript, the % operator can return negative values.

Whenever you subtract and then take mod, use the safe formula: ((a - b) % m + m) % m.

2. Integer overflow during multiplication

Even if a and b are individually less than 10^9 + 7, their product can exceed 2^31 - 1 (the max value of a 32-bit int). You must use a 64-bit type (long in Java, long long in C++) for intermediate multiplication results.

3. Forgetting to take mod after every operation

Some developers compute several additions or multiplications and only take mod at the very end. This can cause overflow in intermediate steps.

4. Using regular division instead of modular inverse

You cannot simply divide and take mod. This is a mathematical property of modular arithmetic, not a language quirk.

5. Applying modular inverse when the modulus is not prime

Fermat's Little Theorem only works when the modulus is prime. If the modulus is not prime, you need the Extended Euclidean Algorithm instead. For most interview problems the modulus is 10^9 + 7 (prime), but always verify.