Powers and Modular Arithmetic

Real-world analogy

What is it?

Powers and modular arithmetic are fundamental tools in competitive programming. A power (a^b) means multiplying a number by itself multiple times, and modulo (%) keeps huge numbers within a manageable range by taking the remainder after division. Together, they let you handle calculations that would otherwise cause integer overflow.

Real-world relevance

Modular arithmetic is everywhere! Clocks use mod 12 (or mod 24). Days of the week use mod 7. Cryptography (like the RSA algorithm that secures the internet) relies heavily on modular exponentiation. Even check digits on credit cards use modular arithmetic to detect typos.

Key points

• What is a Power? — a raised to the power b (written a^b) means multiplying a by itself b times. For example, 2^5 = 2 * 2 * 2 * 2 * 2 = 32. In C++ we can compute this with a simple loop.
• Why Powers Get Huge Fast — Powers grow incredibly fast. 2^10 is already 1024. 2^30 is over a billion. 2^60 overflows even a long long! That is why we need modular arithmetic — to keep numbers small.
• What is Modulo (%)? — The modulo operator (%) gives the remainder after division. 17 % 5 = 2 because 17 divided by 5 is 3 remainder 2. In CP, we often use mod = 1000000007 (a big prime number) to keep answers manageable.
• Modular Addition Rule — (a + b) % m = ((a % m) + (b % m)) % m. This means you can take the modulo at each step instead of waiting until the end. This prevents overflow!
• Modular Multiplication Rule — (a * b) % m = ((a % m) * (b % m)) % m. Just like addition, you can take modulo after each multiplication. This is the key to computing huge powers without overflow.
• Computing Power with Modulo — To compute a^b % m, we multiply a by itself b times, taking modulo at each step. Start with result = 1, then loop b times: result = (result * a) % m. This keeps the number small throughout.
• Fibonacci Numbers — The Fibonacci sequence is 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Each number is the sum of the two before it. fib(n) = fib(n-1) + fib(n-2). Fibonacci numbers grow fast, so we often compute them modulo m.
• Why 1000000007? — The number 1000000007 (often written as 1e9+7) is used in CP because: (1) it is prime, which has nice mathematical properties, (2) it fits in an int, and (3) the product of two numbers mod 1e9+7 fits in a long long.
• Practice Makes Perfect — Try computing 2^10 % 1000 by hand: start with 1, multiply by 2 ten times, take mod 1000 each time. You will get 24. Now try computing fib(10) % 100. Practice these patterns until they feel natural!

Code example

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Computing a^b with modulo
    long long a = 2, b = 10;
    long long mod = 1000000007;
    long long result = 1;
    for (int i = 0; i < b; i++) {
        result = (result * a) % mod;
    }
    cout << a << "^" << b << " mod " << mod << " = " << result << "\n";

    // Fibonacci with modulo
    int n = 20;
    long long fib[21];
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++) {
        fib[i] = (fib[i-1] + fib[i-2]) % mod;
    }
    cout << "fib(" << n << ") = " << fib[n] << "\n";

    // Simple modular arithmetic demo
    long long x = 1000000006, y = 1000000005;
    long long safeSum = ((x % mod) + (y % mod)) % mod;
    cout << "Safe sum mod = " << safeSum << "\n";

    return 0;
}

Line-by-line walkthrough

1. 1. long long a = 2, b = 10; — we set up our base (a=2) and exponent (b=10). We use long long because even intermediate results can be large.
2. 2. long long mod = 1000000007; — this is the standard CP modulo value. It is a prime number just over one billion.
3. 3. long long result = 1; — we start with 1 because anything raised to the power 0 is 1. We will multiply this by a, b times.
4. 4. for (int i = 0; i < b; i++) { result = (result * a) % mod; } — each iteration multiplies result by a and takes modulo. After 10 iterations, result = 2^10 % mod = 1024.
5. 5. fib[0] = 0; fib[1] = 1; — the Fibonacci sequence starts with 0 and 1. These are our base cases.
6. 6. fib[i] = (fib[i-1] + fib[i-2]) % mod; — each Fibonacci number is the sum of the previous two, and we take modulo to prevent overflow.
7. 7. long long safeSum = ((x % mod) + (y % mod)) % mod; — this demonstrates the modular addition rule. Even though x and y are huge, the result fits in a long long.

Spot the bug

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a = 2, b = 40;
    int mod = 1000000007;
    int result = 1;
    for (int i = 0; i < b; i++) {
        result = (result * a) % mod;
    }
    cout << result << "\n";
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Modular Arithmetic for Beginners (CP-Algorithms)
• Modular Arithmetic in Programming (YouTube)
• Fibonacci Problems on CSES (CSES)