➕ Modular Arithmetic: Theory and Practice

📜 Deep Theory of Modular Arithmetic

Modular arithmetic is the arithmetic of remainders. When we say $A \equiv B \pmod M$, we mean that $A$ and $B$ yield the same remainder upon division by $M$, or equivalently: $M$ divides the difference $(A - B)$.

Properties of Congruences

Reflexivity: $A A \pmod M$.
Symmetry: If $A B \pmod M$, then $B A \pmod M$.
Transitivity: If $A B$ and $B C$, then $A C \pmod M$.
Addition/Multiplication: We can add and multiply congruences.
If $A B$ and $C D$, then $A+C B+D$ and $A C B D \pmod M$.

🚀 Fast Modular Exponentiation

Calculating $A^B M$ naively takes $O(B)$ time, which is slow for $B 10^{18}$. We use the "Binary Exponentiation" method, which works in $O(\log B)$.

Idea: $A^{2k} = (A^k)^2$ and $A^{2k+1} = A (A^k)^2$.

long long power(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp % 2 == 1) res = (__int128)res * base % mod; // Use __int128 to avoid overflow during multiplication
        base = (__int128)base * base % mod;
        exp /= 2;
    }
    return res;
}

Note: If mod is up to $10^9$, long long is sufficient. If mod is up to $10^{18}$, the intermediate multiplication may overflow long long, so __int128 is used.

↔ Extended Euclidean Algorithm

The algorithm finds integers $x$ and $y$ that satisfy Bzout's identity: $$A x + B y = \gcd(A, B)$$

How it works (Step by step): We know that $\gcd(A, B) = \gcd(B, A \% B)$. Suppose we have found $x_1, y_1$ for the pair $(B, A \% B)$, i.e.: $$B x_1 + (A \% B) y_1 = \gcd(A, B)$$ Substituting $A \% B = A - \lfloor A/B \rfloor B$: $$B x_1 + (A - \lfloor A/B \rfloor B) y_1 = \gcd$$ $$A y_1 + B (x_1 - \lfloor A/B \rfloor y_1) = \gcd$$ Therefore, the new coefficients are: $x = y_1$ and $y = x_1 - \lfloor A/B \rfloor y_1$.

long long extendedGCD(long long a, long long b, long long &x, long long &y) {
    if (a == 0) {
        x = 0; y = 1;
        return b;
    }
    long long x1, y1;
    long long gcd = extendedGCD(b % a, a, x1, y1);
    x = y1 - (b / a) * x1;
    y = x1;
    return gcd;
}

➗ Modular Division and Inverse Element

The division $A / B M$ is defined as $A B^{-1} M$. The inverse element $B^{-1}$ exists only if $\gcd(B, M) = 1$.

Finding $B^{-1}$:

If $M$ is prime: According to Fermat's Little Theorem, $B^{M-2} M$.
If $M$ is not prime: We use the Extended Euclidean algorithm to solve $B x + M y = 1$. Here $x$ is the sought inverse element (it may be negative, so we take $(x \% M + M) \% M$).

🇨🇳 Chinese Remainder Theorem (CRT)

Allows reconstructing a number $x$ if we know its remainders upon division by several pairwise coprime numbers.

System: $$x a_1 {m_1}$$ $$x a_2 {m_2}$$ ... $$x a_k {m_k}$$

Let $M = m_1 m_2 \dots m_k$. The solution is unique modulo $M$ and is given by the formula: $$x = \left( \sum_{i=1}^{k} a_i M_i y_i \right) \pmod M$$ Where $M_i = M / m_i$, and $y_i$ is the modular inverse of $M_i$ with respect to $m_i$ ($M_i y_i 1 {m_i}$).

Application: Used when working with very large numbers, where operations are performed in parallel with small moduli and the result is finally reconstructed.

👩‍👧 Discrete Logarithm (Baby-step Giant-step)

Task: To find $x$ such that $a^x b m$. This is a difficult task, but the Baby-step Giant-step algorithm solves it in $O(\sqrt{m} \log m)$.

Idea: We represent $x = i k - j$, where $k = \lceil \sqrt{m} \rceil$. The equation becomes $a^{ik - j} b m (a^k)^i b a^j$. 1. We precompute the right-hand side for all $0 j < k$ and store them in a hash table (Baby steps). 2. We compute the left-hand side for $i = 1, \dots, k$ and check for a match in the table (Giant steps).

🧮 Modular Factorial and Binomial Coefficients

Calculating Factorial Modulo

For large $N$, the direct calculation of $N!$ is impossible. We use modular arithmetic.

long long factorialMod(int n, long long mod) {
    long long result = 1;
    for (int i = 2; i <= n; i++) {
        result = (result * i) % mod;
    }
    return result;
}

Binomial Coefficients Modulo

$inom{n}{k} = \frac{n!}{k! (n-k)!}$. To calculate modulo, we use the inverse element.

long long binomialMod(int n, int k, long long mod) {
    if (k > n) return 0;

    vector<long long> fact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i-1] * i) % mod;
    }

    long long denominator = (fact[k] * fact[n - k]) % mod;
    long long inv = power(denominator, mod - 2, mod); // We use Fermat

    return (fact[n] * inv) % mod;
}

Pascal's Triangle

An alternative method for small $N$ and $K$ without using division.

long long pascal[1005][1005];

void buildPascal(int maxN, long long mod) {
    for (int n = 0; n <= maxN; n++) {
        pascal[n][0] = 1;
        for (int k = 1; k <= n; k++) {
            pascal[n][k] = (pascal[n-1][k-1] + pascal[n-1][k]) % mod;
        }
    }
}

🔐 Euler's Theorem (Generalization of Fermat)

For every number $A$ and $M$ where $\gcd(A, M) = 1$: $$A^{\phi(M)} 1 M$$ Where $\phi(M)$ is Euler's totient function (the count of numbers up to $M$ that are coprime to $M$).

Corollary: $A^{-1} A^{\phi(M) - 1} M$.

Euler's Totient Function

int phi(int n) {
    int result = n;
    for (int p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

🎲 Generating Random Numbers Modulo

When working with hash functions and randomized algorithms, generating random numbers is often necessary.

#include <random>

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

long long randomMod(long long mod) {
    return uniform_int_distribution<long long>(0, mod - 1)(rng);
}

🔢 Modular Arithmetic in Matrices

Multiplication of matrices modulo for fast calculation of recurrence relations.

Example: N-th Fibonacci Number in O(log N)

typedef vector<vector<long long>> Matrix;

Matrix multiply(const Matrix& A, const Matrix& B, long long mod) {
    int n = A.size();
    Matrix C(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
            }
        }
    }
    return C;
}

Matrix matrixPower(Matrix A, long long p, long long mod) {
    int n = A.size();
    Matrix result(n, vector<long long>(n, 0));
    for (int i = 0; i < n; i++) result[i][i] = 1; // Identity matrix

    while (p > 0) {
        if (p % 2 == 1) result = multiply(result, A, mod);
        A = multiply(A, A, mod);
        p /= 2;
    }
    return result;
}

long long fibonacci(long long n, long long mod) {
    if (n <= 1) return n;
    Matrix F = {{1, 1}, {1, 0}};
    F = matrixPower(F, n - 1, mod);
    return F[0][0];
}

🧩 Linear Diophantine Equations

Equations of the form $Ax + By = C$.

A solution exists only if $\gcd(A, B)$ divides $C$.

bool linearDiophantine(long long A, long long B, long long C, long long &x, long long &y) {
    long long g = extendedGCD(A, B, x, y);
    if (C % g != 0) return false; // No solution

    // Scaling the solution
    x *= C / g;
    y *= C / g;
    return true;
}

General solution: If $(x_0, y_0)$ is one solution, then all solutions are: $$x = x_0 + \frac{B}{\gcd(A, B)} t$$ $$y = y_0 - \frac{A}{\gcd(A, B)} t$$ Where $t$ is an arbitrary integer.

🏪 Task: Coin Change

We have coins with denominations $c_1, c_2, \ldots, c_k$ and we want to change an amount $S$. How many ways are there?

Solution with Dynamic Programming Modulo

long long coinChange(vector<int>& coins, int S, long long mod) {
    vector<long long> dp(S + 1, 0);
    dp[0] = 1;

    for (int coin : coins) {
        for (int i = coin; i <= S; i++) {
            dp[i] = (dp[i] + dp[i - coin]) % mod;
        }
    }

    return dp[S];
}

🎯 Task: Power Tower

Calculate $A^{B^{C^{}}} M$.

Theorem: If $B \log_2 M$, then $A^B A^{(B \bmod \phi(M)) + \phi(M)} M$.

long long powerTower(long long a, long long b, long long mod) {
    if (mod == 1) return 0;
    if (b == 0) return 1;

    long long phi_m = phi(mod);
    long long exp = powerTower(a, b - 1, phi_m);

    if (b > 1 && a >= log2(mod)) {
        exp += phi_m;
    }

    return power(a, exp, mod);
}

🌟 Common Moduli in Competitions

MOD = 1e9 + 7 (1000000007): Prime number, allows using Fermat's Little Theorem.
MOD = 998244353: Prime number of the form $2^{23} 119 + 1$, has a primitive root, useful for NTT (Number Theoretic Transform).
MOD = 10^9 + 9: Another prime number.

📝 Practical Tips

Always normalize negative numbers:

int normalize(int x, int mod) {
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

Be careful with overflow during multiplication:

long long safeMul(long long a, long long b, long long mod) {
    return (__int128)a * b % mod;
}

Precompute factorials and inverses: When you have many queries for binomial coefficients.

const int MAXN = 1000005;
const long long MOD = 1e9 + 7;
long long fact[MAXN], invFact[MAXN];

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    invFact[MAXN - 1] = power(fact[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--) {
        invFact[i] = invFact[i + 1] * (i + 1) % MOD;
    }
}

long long C(int n, int k) {
    if (k > n || k < 0) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

🧪 Practice Tasks

Exponentiation: Calculate $A^B mod M$ for $B 10^{18}$.
Modular Division: Calculate $rac{A}{B} mod M$ where $M$ is prime.
Factorial: Calculate $N! mod M$ for $N 10^6$.
Binomial Coefficients: Answer $Q$ queries for $inom{N}{K} mod M$.
Fibonacci: Find the $N$-th Fibonacci number modulo $M$ for $N 10^{18}$.
Linear Equation: Solve $Ax C mod M$.
Discrete Logarithm: Find $x$ such that $A^x B mod M$.
Chinese Remainder: Solve a system of congruences.

🏁 Conclusion

Modular arithmetic is at the foundation of encryption algorithms (RSA) and many competitive tasks. Ensure you always handle negative results correctly ((a % n + n) % n) and use long long for intermediate calculations. Fast exponentiation, the inverse element, and the Extended Euclidean algorithm are basic tools that you must master perfectly. The Chinese Remainder Theorem and Euler's Theorem expand the possibilities for working with complex modular tasks. Practice regularly to develop intuition and speed in solving tasks with modular arithmetic.