Modular Arithmetic

Definition: For integers (a) and (b), the expression (a % b) (or (a \mod b)) denotes the remainder when (a) is divided by (b).

Operations:

• Addition: ((a + b) % p).
• Subtraction: ((a - b + p) % p). Adding (p) prevents negative results.
• Multiplication: ((a \times b) % p).
• Division: Cannnot be performed directly; requires the concept of a modular inverse (discussed later).
• Exponentiation: Efficiently computed via fast exponentiation (binary exponentiation).

Modular arithmetic satisfies the associative, commutative, and distributive laws.

Congruence: Definition and Properties

Definition: Two integers (a) and (b) are said to be congruent modulo (m) if they yield the same remainder when divided by (m). This is denoted as (a \equiv b \pmod{m}).

The set of all integers congruent to a given enteger modulo (m) is called a congruence class or residue class. There are exactly (m) distinct congruence classes modulo (m), which together form the complete residue system modulo (m). The reduced residue system modulo (m) consists of the congruence classes represented by integers between (1) and (m) that are coprime to (m). The number of such classes is (\varphi(m)), where (\varphi) is Euler's totient function.

Properties:

1. Symmetry: If (a \equiv b \pmod{m}), then (b \equiv a \pmod{m}).
2. Addition/Subtraction: If (a \equiv b \pmod{m}) and (c \equiv d \pmod{m}), then (a \pm c \equiv b \pm d \pmod{m}).
3. Multiplication: If (a \equiv b \pmod{m}) and (c \equiv d \pmod{m}), then (a \times c \equiv b \times d \pmod{m}).
4. Exponentiation: If (a \equiv b \pmod{m}), then for any positive integer (k), (a^k \equiv b^k \pmod{m}).
5. If (a \equiv b \pmod{m}) and (d) is a common divisor of (a), (b), and (m), then (a \equiv b \pmod{\frac{m}{\gcd(m, d)}}).

Fermat's Little Theorem

If (p) is a prime number, then for any integer (a), (a^p \equiv a \pmod{p}). If additionally (a) is not divisible by (p) (i.e., (\gcd(a, p) = 1)), then (a^{p-1} \equiv 1 \pmod{p}).

Proof Sketch: For prime (p), the numbers (a, 2a, 3a, \dots, (p-1)a) modulo (p) are a permutation of (1, 2, \dots, p-1). Multiplying them together gives ((p-1)! \cdot a^{p-1} \equiv (p-1)! \pmod{p}). Since ((p-1)!) is not divisible by (p), it can be canceled, yielding (a^{p-1} \equiv 1 \pmod{p}).

Euler's Theorem

Let (a) and (n) be positive integers with (\gcd(a, n) = 1). Then, (a^{\varphi(n)} \equiv 1 \pmod{n}), where (\varphi(n)) is Euler's totient function.

Proof Sketch: Let (r_1, r_2, \dots, r_{\varphi(n)}) be a reduced residue system modulo (n). Since (\gcd(a, n)=1), the set (a r_1, a r_2, \dots, a r_{\varphi(n)}) is also a reduced residue system modulo (n). Multiplying the elements of both sets modulo (n) yields the congruence, leading to the theorem.

Fermat's Little Theorem is a special case of Euler's Theorem when (n = p) is prime.

Extended Euler's Theorem: For any integers (a, n, b) with (b \ge \varphi(n)): [ a^b \equiv a^{b \mod \varphi(n) + \varphi(n)} \pmod{n} ] This theorem is useful for modular exponentiation reduction when the exponent is extreme large.

Linear Congruence Equations

Bézout's Identity (Lemma)

For any integers (a) and (b) not both zero, there exist integers (x) and (y) such that: [ a x + b y = \gcd(a, b) ] Furthermore, the greatest common divisor (\gcd(a, b)) is the smallest positive integer that can be expressed as a linear combination of (a) and (b).

Generalization: For integers (a_1, a_2, \dots, a_n), there exist integers (x_1, x_2, \dots, x_n) such that: [ a_1 x_1 + a_2 x_2 + \dots + a_n x_n = \gcd(a_1, a_2, \dots, a_n) ]

Extended Euclidean Algorithm

The Extended Euclidean Algorithm computes integers (x) and (y) satisfying Bézout's Identity: (a x + b y = \gcd(a, b)).

// Returns gcd(a, b) and sets x, y such that a*x + b*y = gcd(a, b)
int extended_gcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int g = extended_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}

Given a particular solution ((x_0, y_0)), the general solution to (a x + b y = \gcd(a, b)) is: [ x = x_0 + \frac{b}{d} \cdot k, \quad y = y_0 - \frac{a}{d} \cdot k ] where (d = \gcd(a, b)) and (k) is any integer. To find the smallest non-negative (x), compute: [ x_{\text{min}} = (x_0 % t + t) % t, \quad \text{where } t = b / d ]

Solving Linear Congruence Equations

A linear congruence equation has the form: [ a x \equiv c \pmod{b} ] It can be rewritten as: [ a x + b y = c ] Let (d = \gcd(a, b)). A solution exists if and only if (d) divides (c). If a solution exists, divide both sides by (d): [ \frac{a}{d} x + \frac{b}{d} y = \frac{c}{d} ] Let (a' = a/d), (b' = b/d), (c' = c/d). Solve (a' x + b' y = 1) using the Extended Euclidean Algorithm to find (x_0). Then (x = c' \cdot x_0) is a particular solution modulo (b).

Example: Find (x) such that (7x \equiv 1 \pmod{26}).

#include <iostream>
using namespace std;
int extended_gcd(int a, int b, int &x, int &y) {
    if (b == 0) { x = 1; y = 0; return a; }
    int g = extended_gcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}
int main() {
    int a = 7, b = 26, x, y;
    int g = extended_gcd(a, b, x, y); // g = gcd(7,26)=1
    // Solution: x mod 26
    int sol = (x % b + b) % b;
    cout << sol << endl; // Outputs 15, since 7*15=105 ≡ 1 mod 26
    return 0;
}

System of Linear Congruences (Chinese Remainder Theorem)

Consider a system: [ \begin{cases} x \equiv a_1 \pmod{m_1} \ x \equiv a_2 \pmod{m_2} \ \vdots \ x \equiv a_n \pmod{m_n} \end{cases} ]

Chinese Remainder Theorem (CRT): If the moduli (m_1, m_2, \dots, m_n) are pairwise coprime, there exists a unique solution modulo (M = m_1 m_2 \cdots m_n). Let (M_i = M / m_i). Compute the modular inverse (t_i) of (M_i) modulo (m_i) (i.e., (M_i t_i \equiv 1 \pmod{m_i})). The solution is: [ x \equiv \sum_{i=1}^n a_i M_i t_i \pmod{M} ]

Extended Chinese Remainder Theorem (ExCRT): Solves the system with out requiring pairwise coprime moduli by iteratively merging congruences. Merge two congruences: [ x \equiv a_1 \pmod{m_1}, \quad x \equiv a_2 \pmod{m_2} ] Rewrite as: [ x = a_1 + k_1 m_1 = a_2 + k_2 m_2 ] [ \Rightarrow k_1 m_1 - k_2 m_2 = a_2 - a_1 ] Let (d = \gcd(m_1, m_2)). A solution exists iff (d) divides (a_2 - a_1). Using the Extended Euclidean Algorithm, find (p, q) such that (m_1 p + m_2 q = d). Then: [ k_1 = \frac{a_2 - a_1}{d} \cdot p ] The merged congruence becomes: [ x \equiv a_1 + k_1 m_1 \pmod{\operatorname{lcm}(m_1, m_2)} ] Repeat this process to merge all equations.

// ExCRT: Merge congruences x ≡ rem[i] mod mod[i]
typedef long long ll;
ll merge_congruences(ll a1, ll m1, ll a2, ll m2) {
    ll p, q;
    ll d = extended_gcd(m1, m2, p, q);
    if ((a2 - a1) % d != 0) return -1; // No solution
    ll lcm = m1 / d * m2;
    ll k = ((a2 - a1) / d * p) % (m2 / d);
    ll x = (a1 + k * m1) % lcm;
    if (x < 0) x += lcm;
    return x; // Returns new remainder, new modulus is lcm
}

Modular Multiplicative Inverse

Definition: For integers (a) and (m) with (\gcd(a, m) = 1), the modular multiplicative inverse of (a) modulo (m) is an integer (x) such that: [ a x \equiv 1 \pmod{m} ] Denoted as (a^{-1} \pmod{m}).

Application: Enables modular division. To compute ((a / b) % m), compute (b^{-1} \pmod{m}) and then evaluate (a \cdot b^{-1} % m).

Computing the Inverse

1. Using Fermat's Little Theorem (Prime Modulus): If (m) is prime and (a \not\equiv 0 \pmod{m}), then: [ a^{-1} \equiv a^{m-2} \pmod{m} ] Compute via fast exponentiation.

int mod_inv_fermat(int a, int prime_mod) {
    return fast_pow(a, prime_mod - 2, prime_mod);
}

2. Using Extended Euclidean Algorithm (General Modulus): Solve (a x + m y = 1). The coefficient (x) modulo (m) is the inverse.

int mod_inv_extended(int a, int m) {
    int x, y;
    int g = extended_gcd(a, m, x, y);
    if (g != 1) return -1; // Inverse does not exist
    return (x % m + m) % m;
}

3. Precomputing Inveress for 1 to n (Prime Modulus): Efficient linear-time precomputation. [ \text{inv}[i] = \left( m - \left\lfloor \frac{m}{i} \right\rfloor \right) \cdot \text{inv}[m % i] % m ] with (\text{inv}[1] = 1).

vector<int> inv(n+1);
inv[1] = 1;
for (int i = 2; i <= n; ++i) {
    inv[i] = (m - (m / i)) * inv[m % i] % m;
}

4. Computing Inverses for an Array of Numbers: Let (\text{pref}[i] = a_1 \cdot a_2 \cdots a_i % m). Compute (\text{suf}[i] = \text{pref}[n]^{-1} \cdot \text{pref}[i-1]^{-1} % m) via suffix products. Then (a_i^{-1} = \text{pref}[i-1] \cdot \text{suf}[i] % m).

vector<int> compute_array_inverses(vector<int> &arr, int mod) {
    int n = arr.size();
    vector<int> pref(n+1, 1), inv_arr(n);
    for (int i = 0; i < n; ++i) pref[i+1] = (pref[i] * arr[i]) % mod;
    int total_inv = mod_inv_fermat(pref[n], mod); // mod is prime
    int suffix = total_inv;
    for (int i = n-1; i >= 0; --i) {
        inv_arr[i] = (pref[i] * suffix) % mod;
        suffix = (suffix * arr[i]) % mod;
    }
    return inv_arr;
}

Order and Primitive Roots

Order: Let (a) and (n) be coprime integers. The order of (a) modulo (n), denoted (\text{ord}_n(a)), is the smallest positive integer (k) such that: [ a^k \equiv 1 \pmod{n} ] By Euler's theorem, (\text{ord}_n(a)) divides (\varphi(n)).

Primitive Root: A number (g) is a primitive root modulo (n) if its order modulo (n) is (\varphi(n)). In other words, the powers (g^1, g^2, \dots, g^{\varphi(n)}) generate all numbers coprime to (n) modulo (n). Primitive roots exist modulo (n) if and only if (n) is (2, 4, p^k,) or (2p^k), where (p) is an odd prime.