Modular Arithmetic

1. Overview and Algorithm

Modular arithmetic involves numbers wrapping around after reaching a certain value—the modulus. It’s used extensively in cryptography, number theory, and competitive programming.

Basic Operations:

• Addition: (a + b) mod m
• Subtraction: (a - b + m) mod m
• Multiplication: (a * b) mod m
• Exponentiation: (a^b) mod m - using Fast Exponentiation
• Modular Inverse: a^-1 mod m - exists if gcd(a, m) = 1

Algorithm: Fast Modular Exponentiation

1. Let result = 1
2. While b > 0:
    a = a % m
    If b is odd: result = (result * a) % m
    a = (a * a) % m
    b = b / 2

Time Complexity:

• Modular Addition, Subtraction, Multiplication: O(1)
• Modular Exponentiation: O(log b)
• Modular Inverse (using Fermat’s Little Theorem): O(log m)

Memory Complexity:

• All operations are done in constant memory, so O(1)

2. Easy Problems

Problem 1: Compute (a + b) mod m

#include <iostream>
using namespace std;

int main() {
    int a = 10, b = 12, m = 7;
    cout << "Result: " << (a + b) % m << endl;
    return 0;
}

Problem 2: Compute (a * b) mod m

#include <iostream>
using namespace std;

int main() {
    int a = 15, b = 4, m = 6;
    cout << "Result: " << (1LL * a * b) % m << endl;
    return 0;
}

3. Intermediate Problems

Problem 1: Modular Exponentiation

Compute (a^b) mod m

#include <iostream>
using namespace std;

long long mod_pow(long long a, long long b, long long m) {
    long long result = 1;
    a = a % m;
    while (b > 0) {
        if (b % 2 == 1)
            result = (result * a) % m;
        a = (a * a) % m;
        b = b / 2;
    }
    return result;
}

int main() {
    cout << mod_pow(2, 10, 1000) << endl;
    return 0;
}

Problem 2: Find Modular Inverse

Using Fermat's Little Theorem: a^m-2 mod m

#include <iostream>
using namespace std;

long long mod_pow(long long a, long long b, long long m) {
    long long res = 1;
    while (b > 0) {
        if (b % 2) res = (res * a) % m;
        a = (a * a) % m;
        b /= 2;
    }
    return res;
}

int mod_inverse(int a, int m) {
    return mod_pow(a, m - 2, m);
}

int main() {
    int a = 3, m = 7;
    cout << "Modular Inverse: " << mod_inverse(a, m) << endl;
    return 0;
}

4. Hard Problem

Problem: Compute nCr % m

Efficient computation using Fermat's Little Theorem when m is prime.

#include <iostream>
using namespace std;

const int MOD = 1e9+7;
const int N = 1e5 + 5;

long long fact[N], inv_fact[N];

long long mod_pow(long long a, long long b, long long m) {
    long long res = 1;
    while (b) {
        if (b % 2) res = res * a % m;
        a = a * a % m;
        b /= 2;
    }
    return res;
}

void preprocess() {
    fact[0] = 1;
    for (int i = 1; i < N; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    inv_fact[N-1] = mod_pow(fact[N-1], MOD-2, MOD);
    for (int i = N-2; i >= 0; i--) {
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
    }
}

long long nCr(int n, int r) {
    if (r > n) return 0;
    return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD;
}

int main() {
    preprocess();
    cout << "10C3 % MOD = " << nCr(10, 3) << endl;
    return 0;
}