Modular Arithmetic

Concept

In heavy mathematical and dynamic programming problems, you will often see this warning:
“Since the answer may be very large, return it modulo $10^9 + 7$.”

Because 32-bit integers cap at 2.14 Billion, and 64-bit floats cap at 9 Quadrillion, computing massive Factorials or Permutations will trigger an Integer Overflow, permanently corrupting your math with negative numbers or a loss of precision.

To fix this, we use Modular Arithmetic.
Modular arithmetic behaves like a clock. If it’s 10:00 AM, and you add 4 hours, it doesn’t become 14:00 AM. It wraps around to 2:00 PM! By applying a modulo ceiling to our math, the numbers never grow large enough to overflow the hardware, but the underlying mathematical relationships between the numbers are perfectly preserved.

The Core Mathematical Properties

You cannot just apply % 1000000007 at the very end of your return statement. The number will have already overflowed inside your loop!

You must apply the modulo operator AT EVERY SINGLE STEP of your calculation.
To do this safely, you must know the algebraic distribution properties of Modulo:

1. Addition is Safe:
(A + B) % M === ((A % M) + (B % M)) % M
If you are running a for loop adding numbers together, you can safely apply % M to the running total on every single iteration.

2. Multiplication is Safe:
(A * B) % M === ((A % M) * (B % M)) % M
Just like addition, you can safely apply % M after every single multiplication step.

3. Division is NOT Safe! (The Trap)
(A / B) % M !== ((A % M) / (B % M)) % M
You absolutely cannot distribute a modulo into a fraction. Division under a modulo requires calculating the Modular Multiplicative Inverse using Fermat’s Little Theorem.
(Note: If a FAANG interview requires you to calculate a Modular Multiplicative Inverse from memory, the interviewer is being exceptionally hostile. It is almost never required unless you are interviewing for a pure cryptography role).

Implementation Example: Massive Factorials

If you are asked to calculate 100! (100 Factorial), the result is a massive 158-digit number that completely shatters all computer memory.

By applying Modular Arithmetic, we can keep the number small while calculating it!

function massiveFactorial(n: number): number {
    const MOD = 1000000007; // 10^9 + 7
    let result = 1;

    for (let i = 1; i <= n; i++) {
        // Apply the modulo AT EVERY STEP of the multiplication!
        result = (result * i) % MOD;
    }

    return result;
}

The Negative Modulo Trap

As mentioned in the Math Concepts section, JavaScript’s % operator is technically a “Remainder” operator, not a true mathematical Modulo.

If you subtract two numbers and apply a modulo, the result might be negative!
A = 5, B = 8, M = 10
(A - B) % M -> (5 - 8) % 10 -> -3 % 10 -> -3.

In true mathematics, clock math cannot be negative. If it’s 5:00 and you go back 8 hours, it’s 9:00! The true answer is 7.
To fix JavaScript’s negative remainder, you must use this specific formula:
((X % M) + M) % M

1. -3 % 10 is -3.
2. -3 + 10 is 7.
3. 7 % 10 is 7.
   The math is perfectly corrected!

Interview Questions

Q: Why do they always use $10^9 + 7$? Why not just $10^{10}$?
A: There are two reasons:

1. It must be Prime: To perform division safely under a modulo (using Fermat’s Little Theorem), the modulo number is mathematically required to be a Prime Number. $10^9 + 7$ is the first easily recognizable, massive prime number.
2. It prevents addition overflow: The maximum 32-bit signed integer is roughly $2 \times 10^9$. If our modulo is $10^9$, then adding two post-modulo numbers together ($10^9 + 10^9 = 2 \times 10^9$) will fit perfectly inside a 32-bit integer without overflowing! If we used a larger modulo, the intermediate addition step would shatter the 32-bit limit before the final % M could compress it.