Modular Arithmetics

Modular arithmetic is a way of doing math where numbers “wrap around” after reaching a certain value — called the modulus.

Think of it like a clock.
After 24 hours, it goes back to the same time again. That’s mod 24 arithmetic!

What does “mod” mean?

When we say a mod m, it means the remainder when a is divided by m.

For example:

Expression	Meaning	Result
`7 mod 3`	7 divided by 3 leaves remainder 1	1
`10 mod 4`	10 divided by 4 leaves remainder 2	2
`15 mod 6`	15 divided by 6 leaves remainder 3	3
`12 mod 12`	12 divided by 12 leaves remainder 0	0

In C++, we use the % operator for this:

#include <iostream>
using namespace std;

int main() {
    cout << 7 % 3 << endl;   // prints 1
    cout << 10 % 4 << endl;  // prints 2
    cout << 10 % 5 << endl;  // prints 0
}

Modular arithmetic in programming

When we work with very large numbers (for example, in combinatorics or cryptography), results can become too big for normal data types.
To get around this, we take everything modulo some number to keep it small and manageable.

A common modulus used in competitive programming is:

MOD = 1'000'000'007  // (a large prime number)

It’s used because:

It fits safely in 64-bit integers.
It avoids overflow when adding up two remainders.
It’s a prime number, which has nice math properties.

Basic modular rules

These rules make modular arithmetic simple to use:

Addition
```
(a + b) % m = (a % m + b % m) % m
```
Subtraction
```
(a - b) % m = ((a % m - b % m) + m) % m
```
We add +m to make sure the result isn’t negative.
Multiplication
```
(a * b) % m = (a % m * b % m) % m
```

Example:

int a = 7, b = 5, m = 3;
cout << (a + b) % m << endl;   // (7 + 5) % 3 = 12 % 3 = 0
cout << (a * b) % m << endl;   // (7 * 5) % 3 = 35 % 3 = 2

Example: Sum of big numbers

#include <iostream>
using namespace std;

int main() {
    const int MOD = 1'000'000'007;
    long long a = 1e12, b = 1e12;
    cout << (a + b) % MOD << endl;
}

Output:

999999979

Even though the sum is 2e12, we safely wrapped it inside MOD.

Handling negatives

Be careful with negative numbers — in C++, % can give negative results.

Example:

cout << (-5) % 3; // prints -2

To fix this, always use:

((a % m) + m) % m

Example:

int a = -5, m = 3;
cout << ((a % m) + m) % m; // prints 1

Modular exponentiation

If you want to compute the remainder of \(a^b\) when divided by \(m\), it’s not efficient to multiply \(a\) many times. Instead, use fast exponentiation.

Fast exponentiation is based on the following observation. If \(b\) is even then \(a^b = (a^{b/2})^2\), and if \(b\) is odd then \(a^b = a \cdot (a^{\lfloor b/2 \rfloor})^2\). This is why we can use a function that recursively calls itself, each time halving the exponent.

long long modpow(long long a, long long b, long long m) {
    if (b == 0) return 1;

    long long half = modpow(a, b / 2, m);
    long long res = (half * half) % m;

    if (b % 2 == 1) { // If b is odd
        res = (res * (a % m)) % m;
    }
    return res;
}

Since \(b\) is halved each time the recursion is called, the total number of recursive calls is \(\lfloor \log_2 b \rfloor + 1\), hence the time complexity of this function is \(O(\log b)\).

Usage:

cout << modpow(2, 10, 1000); // 1024 % 1000 = 24

Modular inverse (optional / advanced)

Sometimes we need to divide numbers under modulo. However, modulo does not distribute over division as it does with the addition and multiplication. So, instead dividing, we multiply by the modular inverse.

From the Fermat’s little theorem we can derive that for a prime modulus \(m\), the modular inverse of \(a\) is

\(a^{-1} \equiv a^{m-2} \mod m\)

int inverse = modpow(a, MOD - 2, MOD);

Then a divided by b with modulus MOD becomes

(a * modpow(b, MOD - 2, MOD)) % MOD

When do we use modular arithmetic?

You’ll see it in problems where:

Numbers grow extremely large (combinations, dynamic programming, etc.)
The result only needs to be given “mod 1e9+7”
You’re implementing math algorithms like power, inverse, or combinatorics

Advantages

Keeps numbers small and avoids overflow
Works with huge results easily
Great for competitive programming problems

Disadvantages

You lose the exact value (only remainder is kept)
Division is tricky — requires modular inverse
Negative results can be confusing in C++

Quick summary

a % m gives the remainder when dividing a by m
Keep using % MOD to avoid overflow in large problems
Use (a + b) % MOD, (a * b) % MOD, and ((a - b) % MOD + MOD) % MOD
For exponentiation, use fast power
For division, use modular inverse when MOD is prime