Modular Arithmetic Basics

The expression a mod b denotes the remainder when a is divided by b.

• Addition: (a + b) % p
• Subtraction: (a - b + p) % p (adding p avoids negative results)
• Multiplication: (a * b) % p
• Division: Not directly supported; requires modular inverses (discussed later)
• Exponentiation: Implemented via fast exponentiation (binary exponentiation)

Modular arithmetic obeys commutative, associative, and distributive laws.

Congruence Relations

If two integers a and b leave the same remainder upon division by m, they are congruent modulo m, written as a ≡ b (mod m).

All integers congruent to a fixed residue modulo m form a congruence class. There are exactly m such classes modulo m, collectively forming a complete residue system.

The subset of residues coprime to m forms the reduced residue system, containing φ(m) elements, where φ is Euler's totient function.

Congruences support addition, multiplication, and exponentiation: if a ≡ b (mod m) and c ≡ d (mod m), then:

• a + c ≡ b + d (mod m)
• a·c ≡ b·d (mod m)
• a^k ≡ b^k (mod m) for any integer k ≥ 0

Fermat’s Little Theorem

If p is prime and a is not divisible by p, then:

a^(p−1) ≡ 1 (mod p)

Equivalently, for any integer a:

a^p ≡ a (mod p)

Proof sketch: Multiplying the set {1, 2, ..., p−1} by a modulo p permutes the set. Taking the product of both sides yields the result after canceling the common factorial term.

Euler’s Theorem

If gcd(a, n) = 1, then:

a^φ(n) ≡ 1 (mod n)

This generalizes Fermat’s theorem (since φ(p) = p−1 for prime p).

Proof idea: Multiplying each element of the reduced residue system modulo n by a yields another reduced residue system. Equating the products gives the result.

Extended Euler’s Theorem (for exponent reduction)

For computing a^b mod n when b is large:

• If gcd(a, n) = 1: a^b ≡ a^(b mod φ(n)) (mod n)
• If gcd(a, n) ≠ 1 and b ≥ φ(n): a^b ≡ a^(b mod φ(n) + φ(n)) (mod n)

This enables efficient computation of huge exponents via recursive totient reduction.

Linear Diophantine Equations and Bézout’s Identity

Bézout’s Identity: For integers a and b (not both zero), there exist integers x and y such that:

a·x + b·y = gcd(a, b)

Moreover, gcd(a, b) is the smallest positive integer expressible in this form.

A corollary: gcd(a, b) = 1 if and only if there exist integers x, y with a·x + b·y = 1.

This extends to multiple integers: the set of all integer linear combinations of a₁, ..., aₙ equals the multiples of gcd(a₁, ..., aₙ).

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int main() { int n, x; cin >> n >> x; for (int i = 1; i < n; ++i) { int y; cin >> y; x = gcd(x, y); } cout << abs(x) << '\n'; }

</details>Extended Euclidean Algorithm
----------------------------

This algorithm computes integers `x` and `y` satisfying Bézout’s identity.

Recurrence derivation:

Let `d = gcd(a, b)`. From the Euclidean step `a = q·b + r` (where `r = a mod b`), we have:

d = gcd(b, r) = b·x₂ + r·y₂ = b·x₂ + (a − q·b)·y₂ = a·y₂ + b·(x₂ − q·y₂)

Thus, if `(x₂, y₂)` solves `b·x + r·y = d`, then `(x, y) = (y₂, x₂ − q·y₂)` solves `a·x + b·y = d`.

Base case: when `b = 0`, then `x = 1`, `y = 0`.

The general solution to `a·x + b·y = d` is:

x = x₀ + (b/d)·k y = y₀ − (a/d)·k for any integer k

To find the minimal positive `x`, compute `x₀ mod (b/d)` and adjust for negativity.

Linear Congruence Equations
---------------------------

An equation of the form:

a·x ≡ c (mod b)

is equivalent to the Diophantine equation:

a·x + b·y = c

By Bézout’s identity, this has integer solutions iff `gcd(a, b) | c`.

To solve:

1. Compute `d = gcd(a, b)`
2. If `d ∤ c`, no solution exists
3. Otherwise, divide through by `d`: `(a/d)·x + (b/d)·y = c/d`
4. Use extended Euclidean algorithm on `a/d` and `b/d` to find a particular solution

<details><summary>Sample code: Solve ax ≡ 1 (mod m)</summary>```
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int64 exgcd(int64 a, int64 b, int64 &x, int64 &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    int64 g = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return g;
}

int main() {
    int64 a, m;
    cin >> a >> m;
    int64 x, y;
    exgcd(a, m, x, y);
    cout << (x % m + m) % m << '\n';  // smallest non-negative solution
}

Given:

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₙ (mod mₙ)

Chinese Remainder Theorem (CRT)

If all moduli mᵢ are pairwise coprime, then there exists a unique solution modulo M = m₁·m₂·...·mₙ.

Construction:

1. Let M = ∏ mᵢ
2. For each i, let Mᵢ = M / mᵢ
3. Find tᵢ such that Mᵢ·tᵢ ≡ 1 (mod mᵢ) (i.e., modular inverse of Mᵢ modulo mᵢ)
4. Solution: x ≡ Σ aᵢ·Mᵢ·tᵢ (mod M)

int64 exgcd(int64 a, int64 b, int64 &x, int64 &y) { if (!b) { x = 1; y = 0; return a; } int64 g = exgcd(b, a % b, y, x); y -= a / b * x; return g; }

int main() { int n; cin >> n; vector a(n), m(n); int64 M = 1; for (int i = 0; i < n; ++i) { cin >> m[i] >> a[i]; M *= m[i]; }

int64 ans = 0;
for (int i = 0; i < n; ++i) {
    int64 Mi = M / m[i], x, y;
    exgcd(Mi, m[i], x, y);
    x = (x % m[i] + m[i]) % m[i];  // ensure positive inverse
    ans = (ans + a[i] * Mi % M * x) % M;
}
cout << ans << '\n';

}

</details>### Extended CRT (non-coprime moduli)

When moduli are not coprime, merge equations pairwise.

Suppose we have:

x ≡ a₁ (mod m₁) x ≡ a₂ (mod m₂)

Express `x = a₁ + k·m₁` and substitute into the second congruence:

a₁ + k·m₁ ≡ a₂ (mod m₂) ⇒ k·m₁ ≡ (a₂ − a₁) (mod m₂)

This is a linear congruence in `k`. Let `d = gcd(m₁, m₂)`. A solution exists iff `d | (a₂ − a₁)`.

If solvable, reduce to:

k·(m₁/d) ≡ (a₂ − a₁)/d (mod m₂/d)

Solve for `k` using extended Euclidean algorithm. Then the combined congruence is:

x ≡ a₁ + k·m₁ (mod lcm(m₁, m₂))

Repeat merging until one congruence remains.

<details><summary>Sample EXCRT implementation</summary>```
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
using i128 = __int128_t;

int64 gcd(int64 a, int64 b) { return b ? gcd(b, a % b) : a; }
int64 lcm(int64 a, int64 b) { return a / gcd(a, b) * b; }

int64 exgcd(int64 a, int64 b, int64 &x, int64 &y) {
    if (!b) { x = 1; y = 0; return a; }
    int64 g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

int main() {
    int n;
    cin >> n;
    vector<i128> a(n), r(n);
    for (int i = 0; i < n; ++i) cin >> a[i] >> r[i];

    i128 cur_a = a[0], cur_r = r[0];
    for (int i = 1; i < n; ++i) {
        i128 a2 = a[i], r2 = r[i];
        i128 c = r2 - cur_r;
        i128 x, y;
        i128 d = exgcd(cur_a, a2, x, y);
        if (c % d != 0) { cout << "-1\n"; return 0; }

        x *= c / d;
        i128 mod = a2 / d;
        x = (x % mod + mod) % mod;

        cur_r += cur_a * x;
        cur_a = lcm(cur_a, a2);
        cur_r = (cur_r % cur_a + cur_a) % cur_a;
    }
    cout << (long long)(cur_r % cur_a) << '\n';
}

The modular inverse of a modulo m is an integer x such that:

a·x ≡ 1 (mod m)

It exists iff gcd(a, m) = 1.

Methods to Compute Inverses

1. Fermat’s method (when m is prime):

a⁻¹ ≡ a^(m−2) (mod m)

Computed via fast exponentiation.

2. Extended Euclidean algorithm (general case):

Solve a·x + m·y = 1; the coefficient x is the inverse.

3. Linear precomputation for 1..n (mod prime p):

Using the recurrence:

inv[1] = 1
inv[i] = (p - p/i) * inv[p % i] % p   for i ≥ 2

4. Batch inversion for arbitrary array a[1..n]:

1. Compute prefix products: s[i] = a[1]·a[2]·...·a[i] mod p
2. Compute inverse of total product: sv[n] = s[n]^(p−2) mod p
3. Backward pass: sv[i−1] = sv[i]·a[i] mod p
4. Then: inv[i] = sv[i]·s[i−1] mod p