Math Fundamentals

AL-08 | Modular arithmetic, fast exponentiation, and GCD/LCM -- the bedrock of every number-theory problem and half of all "implementation" tags on Codeforces.

Difficulty: [Beginner]Prerequisites: Arrays and StringsCF Rating Range: 900-1500

Quick Revisit

• USE WHEN: problem says "answer modulo 10^9+7" or involves large exponents
• INVARIANT: (a op b) mod m = ((a mod m) op (b mod m)) mod m for op in
• TIME: O(log n) for modpow, O(log min(a,b)) for GCD | SPACE: O(1)
• CLASSIC BUG: intermediate overflow -- cast to long long before multiplying: (1LL * a * b) % m
• PRACTICE: see practice problems in this chapter

Contents

• Intuition
• C++ STL Reference
• Implementation (Contest-Ready)
• Operations Reference
• Problem Patterns & Tricks
• Contest Cheat Sheet
• Gotchas & Debugging
• Self-Test
• Practice Problems
• Further Reading

---

Intuition

Layer 1 -- The Pain

You need to compute $n!mod({10}^9+7)$ for $n=200000$. Naive approach: multiply everything first, mod at the end.

// BROKEN -- overflows almost immediately
long long factorial = 1;
for (int i = 2; i <= 200000; i++)
    factorial *= i;              // overflow after ~20 iterations
factorial %= 1000000007;         // too late, garbage value

Even long long maxes out at roughly $9.2\times {10}^{18}$. By $i=21$ the product $21!\approx 5.1\times {10}^{19}$ already wraps around. The final % MOD operates on meaningless bits -- the answer is wrong and there is no compiler warning.

Layer 2 -- The Key Insight

Modular arithmetic lets you reduce at every step because the ring operations distribute over mod.

The core identities:

• $(a+b)modm=((amodm)+(bmodm))modm$
• $(a\cdot b)modm=((amodm)\cdot (bmodm))modm$
• $(a-b)modm=((amodm)-(bmodm)+m)modm$

Analogy -- clock arithmetic. A 12-hour clock wraps every 12: "10 o'clock plus 5 hours" is 3, not 15. Modular arithmetic is the same wrapping applied to any modulus $m$. After every operation you fold back into $[0,m-1]$, so intermediate values never escape that range.

Caution: Modular division is not real division

$(a/b)modm\ne (amodm)/(bmodm)$. Division requires the modular inverse $b^{-1}$ such that $b\cdot b^{-1}\equiv 1(\mathrm{mod}m)$, computed via Fermat ($b^{m-2}modm$ when $m$ is prime) or the extended Euclidean algorithm. This is the single most common beginner math bug — a stray / in a modular expression is silently wrong.

Layer 3 -- Visual Walkthrough

Computing $6!mod1000000007$ step by step, reducing after every multiplication:

  MOD = 1000000007

  Step 1:  result = 1 * 2           =          2   ( < MOD, no wrap )
  Step 2:  result = 2 * 3           =          6   ( < MOD, no wrap )
  Step 3:  result = 6 * 4           =         24   ( < MOD, no wrap )
  Step 4:  result = 24 * 5          =        120   ( < MOD, no wrap )
  Step 5:  result = 120 * 6         =        720   ( < MOD, no wrap )

  After every step the intermediate value is at most
  (MOD - 1) * n  <  10^9 * 2*10^5  =  2*10^14  <<  9.2*10^18 (long long max)

  No overflow at any point.  Final answer: 720

For larger $n$ the per-step product stays bounded by $(m-1{)}^2<{10}^{18}$, which fits in long long. When $m$ can be up to ${10}^{18}$ itself, use (__int128) for the intermediate product.

  +------+------+---------------------+---------+
  | Step |  i   | result * i          | % MOD   |
  +------+------+---------------------+---------+
  |  1   |  2   |   1 * 2 = 2         |    2    |
  |  2   |  3   |   2 * 3 = 6         |    6    |
  |  3   |  4   |   6 * 4 = 24        |   24    |
  |  4   |  5   |  24 * 5 = 120       |  120    |
  |  5   |  6   | 120 * 6 = 720       |  720    |
  +------+------+---------------------+---------+
  Invariant: after every row, result is in [0, MOD-1].

Worked Example: Euclidean Algorithm -- gcd(252, 105)

  Step |  a   |  b   | a = q x b + r          | Next call
  -----|------|------|------------------------|-----------------
    1  | 252  | 105  | 252 = 2 x 105 + 42    | gcd(105, 42)
    2  | 105  |  42  | 105 = 2 x  42 + 21    | gcd( 42, 21)
    3  |  42  |  21  |  42 = 2 x  21 +  0    | gcd( 21,  0)
    4  |  21  |   0  | b = 0, done            | -> gcd = 21

  3 divisions.  Compare: trial division would scan 105 candidates.

Worked Example: Extended Euclidean -- find x, y with 252x + 105y = 21

Preview only. Extended Euclidean is covered in full in 03-extended-euclid-crt.md, including iterative implementation, modular inverse for non-prime moduli, and CRT. The trace below is just enough to motivate "GCD as a linear combination" so the modular-inverse formula later in this file does not appear out of nowhere.

  Back-substitute from the Euclidean steps:

  Step 3:  21 = 105 - 2 x 42
  Step 2:  42 = 252 - 2 x 105

  Substitute Step 2 into Step 3:
    21 = 105 - 2 x (252 - 2 x 105)
       = 105 - 2 x 252 + 4 x 105
       = 5 x 105 - 2 x 252

  Result:  x = -2,  y = 5
  Check:   252 x (-2) + 105 x 5 = -504 + 525 = 21  OK

  Tabular form (computing coefficients forward):
  | Step | r   | q | x   | y   | Equation                |
  |------|-----|---|-----|-----|-------------------------|
  |  --   | 252 | -- |  1  |  0  | 252 = 1*252 + 0*105    |
  |  --   | 105 | -- |  0  |  1  | 105 = 0*252 + 1*105    |
  |  1   |  42 | 2 |  1  | -2  | 42 = 252 - 2*105       |
  |  2   |  21 | 2 | -2  |  5  | 21 = 105 - 2*42        |
  |  3   |   0 | 2 |  --  |  --  | done                    |

Worked Example: Modular Inverse via Fermat -- 3⁻¹ mod 7

  7 is prime, so by Fermat's little theorem:
    3⁻¹ ≡ 3^(7-2) = 3⁵  (mod 7)

  Binary exponentiation of 3⁵ mod 7:
    5 = (101)₂

  | Step | bit | exp | result           | base             |
  |------|-----|-----|------------------|------------------|
  |  0   |  --  |  5  | 1                | 3                |
  |  1   |  1  |  5  | 1 x 3 = 3       | 3² = 9 ≡ 2      |
  |  2   |  0  |  2  | 3 (unchanged)    | 2² = 4           |
  |  3   |  1  |  1  | 3 x 4 = 12 ≡ 5  | 4² = 16 ≡ 2     |

  3⁵ mod 7 = 5
  Verify: 3 x 5 = 15 = 2 x 7 + 1 ≡ 1 (mod 7)  OK

Layer 4 -- The Invariant

+------------------------------------------------------------------+
|  INVARIANT: At every step, the intermediate result lies in       |
|  [0, m-1].  Addition, subtraction, and multiplication preserve   |
|  this range because we apply  % m  after each operation.         |
|                                                                  |
|  Proof sketch (multiplication):                                  |
|    0 <= a, b < m                                                 |
|    => 0 <= a * b < m^2                                           |
|    => 0 <= (a * b) % m < m                        QED            |
+------------------------------------------------------------------+

Look back at the walkthrough table: after Step 3 the result is 24 -- less than ${10}^9+7$. After Step 5 it is 720 -- still in $[0,m-1]$. The invariant holds at every row, which is exactly why the intermediate values never overflow long long.

Layer 5 -- When to Reach for This

Trigger phrases in problem statements:

• "Print the answer modulo ${10}^9+7$."
• "Since the answer can be large..."
• Any counting / combinatorics problem (paths, subsequences, colorings).
• Matrix exponentiation (the entries grow exponentially without mod).
• Hashing (polynomial rolling hash is arithmetic mod a prime).

Counter-examples -- when modular arithmetic is NOT the tool:

• The problem asks for the exact integer answer (e.g., GCD, min/max).
• Floating-point geometry or probability with real-valued output.
• Problems where $n$ is small enough that the answer fits in long long without wrapping (no "modulo" instruction in the statement).

---

What the Code Won't Teach You

The modpow template works. What it does not explain:

Why % MOD after every step is safe. Modular arithmetic preserves addition and multiplication because $\mathbb{Z}/m\mathbb{Z}$ is a ring -- the algebraic structure where these two operations close. Division does not close: $a/b(\mathrm{mod}m)$ is not $(amodm)/(bmodm)$. Once you internalize "ring yes, field only when $m$ is prime," you will never again wonder whether a particular modular shortcut is legal.

Binary exponentiation is a framework, not a function. The template works for any operation that is associative and has an identity element. Scalar multiplication $modp$, matrix multiplication, function composition, polynomial product -- all valid. Recognizing "repeated application of an associative operation" as a binary-exponentiation target is a meta-skill that unlocks matrix exponentiation, segment-tree composition, and more.

BINARY EXPONENTIATION -- ONE TEMPLATE, MANY TYPES:

  +---------------------+-------------------+---------------+
  |  combine(a, b)      |  identity         |  use case     |
  +---------------------+-------------------+---------------+
  |  a * b % MOD        |  1                |  modpow       |
  |  mat_mul(A, B)      |  I (identity mat) |  matrix expo  |
  |  compose(f, g)      |  id function      |  seg-tree     |
  |  poly_mul(P, Q)     |  [1]              |  poly power   |
  +---------------------+-------------------+---------------+

  All require: combine is associative + identity exists.

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
__gcd(a, b)	<algorithm>	GCD of a and b (pre-C++17, GCC extension)	$O(\log (min(a,b)))$
gcd(a, b)	<numeric>	GCD of a and b (C++17 standard)	$O(\log (min(a,b)))$
lcm(a, b)	<numeric>	LCM of a and b (C++17 standard)	$O(\log (min(a,b)))$
__int128	built-in	128-bit integer (GCC/Clang), no cin/cout support	--
__builtin_ctzll(x)	built-in	Count trailing zeros (useful for binary GCD)	$O(1)$

Notes:

• gcd(0, 0) returns 0 in C++17.
• lcm(a, b) can overflow if $a\cdot b/gcd(a,b)$ exceeds the type. Use long long.
• __gcd with negative arguments has implementation-defined behavior -- prefer gcd (C++17).

---

Implementation (Contest-Ready)

Version 1: Minimal Contest Template

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

using ll = long long;
const ll MOD = 1e9 + 7;

ll modpow(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = (__int128)result * base % mod;
        base = (__int128)base * base % mod;
        exp >>= 1;
    }
    return result;
}

ll modinv(ll a, ll mod) {
    return modpow(a, mod - 2, mod); // mod must be prime
}

ll safe_mod(ll a, ll mod) {
    return ((a % mod) + mod) % mod;
}

// Overflow-safe LCM
ll safe_lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Example: compute 2^10 mod (10^9+7)
    cout << modpow(2, 10, MOD) << "\n"; // 1024

    // Example: modular inverse of 3 mod (10^9+7)
    ll inv3 = modinv(3, MOD);
    cout << inv3 << "\n";
    cout << (3LL * inv3 % MOD) << "\n"; // 1

    // Example: GCD / LCM
    cout << gcd(48LL, 18LL) << "\n";     // 6
    cout << safe_lcm(48LL, 18LL) << "\n"; // 144
}

Version 2: Explained -- Modular Arithmetic Toolkit

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

using ll = long long;
const ll MOD = 1e9 + 7;

// Binary exponentiation: compute base^exp % mod in O(log exp).
// Uses __int128 for intermediate multiplication to prevent overflow
// when mod can be up to ~10^18.
ll modpow(ll base, ll exp, ll mod) {
    ll result = 1;
    base %= mod;
    // If base was negative, make it positive
    if (base < 0) base += mod;
    while (exp > 0) {
        // If the lowest bit of exp is set, multiply result by base
        if (exp & 1)
            result = (__int128)result * base % mod;
        // Square the base for the next bit position
        base = (__int128)base * base % mod;
        // Shift exp right by 1 (move to next bit)
        exp >>= 1;
    }
    return result;
}

// Modular inverse using Fermat's little theorem: a^(-1) = a^(p-2) mod p.
// Only works when mod is PRIME. For composite mod, use extended Euclidean.
ll modinv(ll a, ll mod) {
    return modpow(a, mod - 2, mod);
}

// Extended Euclidean algorithm: finds x, y such that a*x + b*y = gcd(a, b).
// Returns gcd(a, b). Works for any a, b (including composite moduli).
ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll x1, y1;
    ll g = extgcd(b, a % b, x1, y1);
    // Back-substitute: x = y1, y = x1 - (a/b)*y1
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// Modular inverse via extended Euclidean -- works for any mod
// where gcd(a, mod) == 1 (not just primes).
ll modinv_ext(ll a, ll mod) {
    ll x, y;
    ll g = extgcd(a, mod, x, y);
    // Inverse exists only if gcd(a, mod) == 1
    assert(g == 1);
    return ((x % mod) + mod) % mod;
}

// Safe modular subtraction: handles negative values from C++ % operator.
// C++ guarantees (a % m) has the same sign as a, so a - b can go negative.
ll safe_mod(ll a, ll mod) {
    return ((a % mod) + mod) % mod;
}

// Overflow-safe LCM: divide BEFORE multiply to avoid intermediate overflow.
// a / gcd(a,b) fits in long long, then multiply by b.
ll safe_lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

// Precompute factorials and inverse factorials for nCr queries in O(1).
// Call init_factorials(max_n) once, then use nCr(n, r).
const int MAXN = 2e6 + 5;
ll fac[MAXN], inv_fac[MAXN];

void init_factorials(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i % MOD;
    // Compute inverse of n! using Fermat, then walk backwards:
    // inv_fac[i] = inv_fac[i+1] * (i+1) % MOD
    inv_fac[n] = modpow(fac[n], MOD - 2, MOD);
    for (int i = n - 1; i >= 0; i--)
        inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;
}

ll nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fac[n] % MOD * inv_fac[r] % MOD * inv_fac[n - r] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Demo: modpow
    cout << modpow(3, 13, 1000) << "\n"; // 323

    // Demo: modular inverse (Fermat)
    ll inv3 = modinv(3, MOD);
    cout << (3LL * inv3 % MOD) << "\n"; // 1

    // Demo: modular inverse (extended Euclidean, non-prime mod)
    ll inv3_ext = modinv_ext(3, 100); // gcd(3,100)=1, so inverse exists
    cout << (3LL * inv3_ext % 100) << "\n"; // 1

    // Demo: nCr with precomputed factorials
    init_factorials(1000);
    cout << nCr(10, 3) << "\n"; // 120
    cout << nCr(1000, 500) << "\n"; // large number mod 10^9+7
}

---

Operations Reference

Operation	Time	Space
modpow(a, n, m)	$O(\log n)$	$O(1)$
modinv(a, m) (Fermat)	$O(\log m)$	$O(1)$
extgcd(a, b)	$O(\log (min(a,b)))$	$O(\log (min(a,b)))$ stack
gcd(a, b)	$O(\log (min(a,b)))$	$O(1)$
lcm(a, b)	$O(\log (min(a,b)))$	$O(1)$
init_factorials(n)	$O(n+\log m)$	$O(n)$
nCr(n, r) after init	$O(1)$	--
Matrix exponentiation ($k\times k$ matrix, power $n$)	$O(k^3\log n)$	$O(k^2)$

---

Problem Patterns & Tricks

Pattern 1: Modular Arithmetic -- "Print Answer mod ${10}^9+7$"

The most common pattern. Any time you see "output modulo ${10}^9+7$," you need to mod at every step. Key rule: mod after every addition and multiplication. For division, use modular inverse.

// Accumulating a product mod p
ll prod = 1;
for (int i = 0; i < n; i++)
    prod = prod * a[i] % MOD;

// Division: multiply by inverse instead
ll ans = prod % MOD * modinv(divisor, MOD) % MOD;

CF examples: CF 1278C, CF 1744D

---

Pattern 2: Fast Exponentiation for Counting

BINARY EXPONENTIATION -- BIT SCAN OF 2^10:

  10 = 1010 in binary

  +------+---------+--------------+-------------------+
  | Step | bit     | base         | result             |
  +------+---------+--------------+-------------------+
  |  0   | 0 (off) | 2^1 = 2     | 1  (unchanged)     |
  |  1   | 1 (ON)  | 2^2 = 4     | 1 * 4 = 4          |
  |  2   | 0 (off) | 2^4 = 16    | 4  (unchanged)     |
  |  3   | 1 (ON)  | 2^8 = 256   | 4 * 256 = 1024     |
  +------+---------+--------------+-------------------+
  Answer: 2^10 = 1024       (2 squarings used, 2 multiplies)

Many counting problems reduce to computing $a^{n}modm$. Examples: number of binary strings of length $n$, number of ways to tile a board, geometric series sums.

// How many subsets of a set of size n? Answer: 2^n mod MOD
cout << modpow(2, n, MOD) << "\n";

CF examples: CF 630I, CF 1538D

---

Pattern 3: GCD Reduction / "GCD Equals K"

Problems asking "how many pairs have GCD equal to $k$?" or "find the array element that shares a factor with all others." Reduce by dividing all elements by $k$ and counting coprime pairs.

// GCD of entire array
ll g = 0;
for (int x : a) g = gcd(g, (ll)x);

The Euclidean algorithm that powers gcd() converges remarkably fast -- each pair of steps at least halves the smaller argument:

    GCD EUCLIDEAN ALGORITHM:  gcd(48, 18)

    +------+------+---------------------------+
    | a    | b    | operation                 |
    +------+------+---------------------------+
    |  48  |  18  | 48 = 2*18 + 12            |
    |      |      |   v                       |
    |  18  |  12  | 18 = 1*12 + 6             |
    |      |      |   v                       |
    |  12  |   6  | 12 = 2*6  + 0             |
    |      |      |   v                       |
    |   6  |   0  | b=0, DONE ---> gcd = 6    |
    +------+------+---------------------------+

    48 ---> 18 ---> 12 ---> 6 ---> 0
       \       \       \       \
        each step: a mod b shrinks fast
        (at least halves every 2 steps)
        Total: O(log min(a,b)) steps

CF examples: CF 1459C, CF 1462A

---

Pattern 4: Precomputed Factorials for $(\genfrac{}{}{0ex}{}{n}{r})$ Queries

When a problem needs many binomial coefficient queries (combinatorics, inclusion-exclusion), precompute $n!$ and $(n!{)}^{-1}$ up front. Then each query is $O(1)$.

init_factorials(200000);
// Answer each query in O(1)
for (auto [n, r] : queries)
    cout << nCr(n, r) << "\n";

CF examples: CF 1462D, CF 1549D

---

Pattern 5: Matrix Exponentiation for Linear Recurrences

Any linear recurrence $f(n)=c_{1}f(n-1)+c_{2}f(n-2)+\dots$ can be computed in $O(k^3\log n)$ using matrix exponentiation, where $k$ is the recurrence order. Classic example: Fibonacci in $O(\log n)$.

using Mat = vector<vector<ll>>;

Mat mul(const Mat& A, const Mat& B, ll mod) {
    int n = A.size();
    Mat C(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++)
        for (int k = 0; k < n; k++) if (A[i][k])
            for (int j = 0; j < n; j++)
                C[i][j] = (C[i][j] + (__int128)A[i][k] * B[k][j]) % mod;
    return C;
}

Mat matpow(Mat A, ll p, ll mod) {
    int n = A.size();
    Mat R(n, vector<ll>(n, 0));
    for (int i = 0; i < n; i++) R[i][i] = 1; // identity
    while (p > 0) {
        if (p & 1) R = mul(R, A, mod);
        A = mul(A, A, mod);
        p >>= 1;
    }
    return R;
}

// Fibonacci: F(n) via [[1,1],[1,0]]^n
ll fib(ll n) {
    if (n <= 1) return n;
    Mat M = {{1, 1}, {1, 0}};
    Mat R = matpow(M, n - 1, MOD);
    return R[0][0];
}

CF examples: CF 185A, CF 1182E

---

Pattern 6: Euler's Totient and Generalized Exponent Reduction

When the exponent is huge (given as a string or $a^{b^c}$), use Euler's theorem: $a^n\equiv a^{nmod\varphi (m)}(\mathrm{mod}m)$ when $gcd(a,m)=1$. For $m$ prime, $\varphi (m)=m-1$.

// Read exponent as string, compute exp mod (MOD-1)
string s; cin >> s;
ll exp_mod = 0;
for (char c : s)
    exp_mod = (exp_mod * 10 + (c - '0')) % (MOD - 1);
cout << modpow(a, exp_mod, MOD) << "\n";

CF examples: CF 1117D, CF 906D

---

Contest Cheat Sheet

+--------------------------------------------------------------+
|                  MATH FUNDAMENTALS CHEAT SHEET               |
+--------------------------------------------------------------+
| MODPOW:                                                      |
|   ll modpow(ll b, ll e, ll m) {                              |
|     ll r=1; b%=m;                                            |
|     while(e>0){if(e&1)r=(__int128)r*b%m;                     |
|       b=(__int128)b*b%m; e>>=1;} return r; }                 |
+--------------------------------------------------------------+
| MODINV (prime mod):  modinv(a,m) = modpow(a, m-2, m)        |
+--------------------------------------------------------------+
| GCD / LCM:                                                   |
|   #include <numeric>  // C++17                               |
|   gcd(a,b);  lcm(a,b);                                      |
|   safe: a / gcd(a,b) * b   (divide first!)                  |
+--------------------------------------------------------------+
| OVERFLOW PREVENTION:                                         |
|   (__int128)a * b % m       // safe up to 10^18 * 10^18     |
|   Use ll (long long) not int for a*b > 2^31                  |
+--------------------------------------------------------------+
| NEGATIVE MOD FIX:  ((a % m) + m) % m                        |
+--------------------------------------------------------------+
| nCr (precomputed):                                           |
|   fac[0]=1; for i=1..n: fac[i]=fac[i-1]*i%MOD;             |
|   inv_fac[n]=modpow(fac[n],MOD-2,MOD);                      |
|   for i=n-1..0: inv_fac[i]=inv_fac[i+1]*(i+1)%MOD;         |
|   nCr(n,r) = fac[n]*inv_fac[r]%MOD*inv_fac[n-r]%MOD        |
+--------------------------------------------------------------+
| MATRIX EXPO:  same as modpow but with matrix multiplication  |
|   Use for linear recurrences in O(k^3 log n)                |
+--------------------------------------------------------------+

---

Gotchas & Debugging

Gotcha 1: Overflow from a * b % m

If a and b are both up to ${10}^{18}$, their product overflows long long ($2^{63}\approx 9.2\times {10}^{18}$). Fix:

// WRONG -- overflows when a, b ~ 10^18
ll result = a * b % m;

// RIGHT -- __int128 handles up to ~1.7 * 10^38
ll result = (__int128)a * b % m;

Gotcha 2: Negative Modular Result in C++

C++ % preserves the sign of the dividend. So -7 % 3 == -1, not 2.

// WRONG -- can return negative values
int r = a % m;

// RIGHT
int r = ((a % m) + m) % m;

Gotcha 3: Mod Before Multiply, Not After

Don't accumulate a huge product and then mod. Mod at each step.

// WRONG -- product overflows long before you mod
ll prod = 1;
for (int i = 0; i < n; i++) prod *= a[i];
prod %= MOD;

// RIGHT
ll prod = 1;
for (int i = 0; i < n; i++) prod = prod * a[i] % MOD;

Gotcha 4: modinv Requires gcd(a, m) == 1

Fermat's little theorem needs m to be prime and a not divisible by m. If a % m == 0, the inverse doesn't exist. For composite m, use extended Euclidean.

WHEN DOES MODULAR INVERSE EXIST?

  gcd(a, m) == 1  -->  inverse EXISTS
                       +-- m is prime? --> Fermat: a^(m-2) mod m
                       +-- m composite? -> ExtGCD: solve a*x + m*y = 1

  gcd(a, m) > 1   -->  inverse DOES NOT EXIST
                        (e.g., a=4, m=6: gcd=2, no x satisfies 4x = 1 mod 6)

Gotcha 5: LCM Overflow

// WRONG -- a * b overflows before the division
ll l = a * b / gcd(a, b);

// RIGHT -- divide first, then multiply
ll l = a / gcd(a, b) * b;

Gotcha 6: Forgetting to Handle exp == 0

$a^0=1$ for all $a$ (including $a=0$ in contest math). The modpow template handles this correctly since result starts at 1 and the loop doesn't execute. But make sure your calling code doesn't special-case it incorrectly.

Gotcha 7: Using int Instead of long long

When $n\le {10}^5$ but $a_i\le {10}^9$, a sum or product easily exceeds int range. Default to long long in contests.

Debugging Tips

• Wrong answer on mod problems? Print intermediate values without mod to verify logic, then add mod back.
• Runtime error in modinv? Check that a % m != 0 and m is prime (for Fermat).
• Off-by-one in nCr? Verify init_factorials was called with a large enough bound.
• Matrix expo gives wrong answer? Test your recurrence on small cases ($n=0,1,2,3$) by hand.

Mental Traps

"I know modular arithmetic, so I can skip this section." Modular arithmetic at the basic level (add, subtract, multiply with % MOD) is simple. The traps hide in the edges: modular inverse only exists when gcd(a, MOD) = 1, division requires inverse (not /), and the algebraic rules for % and / don't carry over from integer arithmetic. "I know it" and "I always apply it correctly under contest pressure" are very different things.

"GCD and LCM are the same computation, just different formula." Correct formula: lcm(a, b) = a / gcd(a, b) * b. Note the division before multiplication -- a * b / gcd(a, b) overflows when a and b are large. Dividing first avoids this. Getting the order wrong silently overflows and produces a valid-looking but incorrect number.

"Binary exponentiation is just fast powers." It is also the foundation of modular inverse (via Fermat's little theorem), matrix exponentiation for linear recurrences, and polynomial hashing. Not understanding why it is correct (the exponentiation-by-squaring structure over any associative operation) means you will implement variations wrong -- e.g., when the base is a matrix or when you need the full sequence of powers.

"I can use sqrt() from <cmath> to check perfect squares." Floating-point sqrt(x) can return a value like $n-{10}^{-14}$, which truncates to $n-1$. For exact perfect-square checks, compute s = (long long)sqrtl(x) and then verify both $s^2\le x$ and $(s+1{)}^2>x$. The trap is that sqrt usually works in testing and fails on the one edge case the judge has.

PERFECT SQUARE CHECK -- THE TRAP:

  x = 10^18          sqrt(x) ~ 999999999.9999999...
  (long long)sqrt(x) might be 999999999   <-- WRONG (off by 1)

  Safe pattern:
  +-----------------------------------------------+
  | long long s = sqrtl(x);                       |
  | while (s * s > x) s--;                        |
  | while ((s+1)*(s+1) <= x) s++;                 |
  | bool is_perfect = (s * s == x);               |
  +-----------------------------------------------+

"Overflow only matters when numbers are close to ${10}^{18}$." Two int values near ${10}^9$ multiply to $\sim {10}^{18}$ -- that fits in long long. But three such values multiplied (${10}^{27}$) do not. In chains like a * b % MOD * c % MOD, the first a * b can overflow int silently if a and b are int. The fix: cast early ((long long)a * b % MOD). This trap bites in cumulative expressions, not just in single big multiplications.

---

Common Mistakes

1. Intermediate overflow. (a * b) % m overflows if a and b are int. Cast first: (1LL * a % m * b) % m.
2. Negative mod in C++. (-3) % 7 evaluates to -3, not 4. Fix: ((a % m) + m) % m.
3. Modular division without inverse. (a / b) % m is NOT (a % m) / (b % m). You must compute b's modular inverse: a * mod_inverse(b, m) % m.
4. Forgetting mod at every step. A single missed mod in a chain of operations can cause overflow and wrong answers even if the final mod is correct.
5. Using pow() from <cmath>. Floating-point pow is imprecise for large integers. Always use integer binary exponentiation with mod.
6. Trusting a transition matrix on first try. For matrix exponentiation of a linear recurrence, never submit a transition matrix you wrote in one pass. Validate against brute force: print M^1 * v0, M^2 * v0, M^3 * v0 and compare to the first 5 values computed directly. If they diverge at step 1, your matrix is wrong; if they diverge later, your base vector is wrong. Two minutes of validation saves thirty minutes of debugging.

Debug Drills

Drill 1. Overflow in modular multiplication.

long long mod_mul(long long a, long long b, long long mod) {
    return a * b % mod;  // What's wrong?
}

What's wrong?

When a and b are up to 10^18, a * b overflows long long (max ~9.2 x 10^18). Fix: use (__int128)a * b % mod or split into halves.

Drill 2. Negative modular result.

long long mod_sub(long long a, long long b, long long mod) {
    return (a - b) % mod;  // What's wrong?
}

What's wrong?

If a < b, the result is negative, and C++ % preserves the sign. Fix: return (a - b % mod + mod) % mod;

Drill 3. Wrong base case in binary exponentiation.

long long power(long long a, long long n, long long mod) {
    long long res = 0;  // What's wrong?
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

What's wrong?

res should be initialized to 1, not 0. With res = 0, multiplication keeps it at 0 forever. The identity element for multiplication is 1.

---

Self-Test

Without looking at the implementations above, you should be able to answer these:

1. Write binary exponentiation from memory -- compute a^b % m in $O(\log b)$, correctly handling b = 0. What is the key loop invariant?

2. Write gcd(a, b) from memory -- using the recursive Euclidean algorithm -- and extend it to lcm(a, b) without overflow. Why must you divide before multiplying?

3. State when modular inverse exists -- under what condition on $gcd(a,m)$? Give two methods to compute it (one for prime $m$, one for general $m$).

4. Fix this buggy code: int ans = a * b % MOD; where a, b are up to ${10}^9$. Explain exactly why it is wrong and provide the corrected version.

5. State the rule for modular subtraction -- why does (a - b) % MOD need a + MOD before the outer % in C++? What value would (-5) % 7 produce?

6. Trace modpow(2, 10, 1000) by hand -- write out each iteration showing the binary decomposition of the exponent, the running result, and the squared base.

7. When can you NOT use modpow(a, m-2, m) for inverse? Give a concrete example where this formula silently produces a wrong answer.

Quick Checkpoints

• [ ] I can write modpow(base, exp, mod) from scratch in under 60 seconds
• [ ] I know two methods to compute modular inverse and when each applies
• [ ] I can spot the overflow bug in int ans = a * b % MOD instantly
• [ ] I can compute $(\genfrac{}{}{0ex}{}{n}{k})modp$ in $O(1)$ after $O(n)$ precomputation
• [ ] I understand why (a - b) % MOD needs + MOD and can give a concrete failing example

---

Practice Problems

Rating	You should be able to...
CF 1200	Compute a^b mod m using binary exponentiation without overflow
CF 1500	Use Fermat's little theorem for modular inverse; precompute factorial tables
CF 1800	Apply Euler's theorem for a^(b^c) mod m; handle non-prime moduli
CF 2100	Chain matrix exponentiation for recurrences; use __int128 or Montgomery multiplication for tight TL

#	Problem	Source	Difficulty	Key Idea
1	Watermelon	CF 4A	Easy (800)	Basic divisibility check
2	GCD and LCM	CSES	Easy (900)	Direct GCD/LCM computation
3	Exponentiation	CSES	Easy (1000)	Binary exponentiation template
4	Exponentiation II	CSES	Medium (1300)	$a^{b^c}modm$ using Euler's theorem
5	Fibonacci Numbers	CSES	Medium (1500)	Matrix exponentiation
6	Row GCD	CF 1459C	Medium (1600)	GCD properties, difference trick
7	Magic Gems	CF 1117D	Medium (1600)	Linear recurrence + matrix expo
8	Plant	CF 185A	Medium-Hard (1800)	Matrix exponentiation on ternary recurrence
9	Power Tower	CF 906D	Hard (2200)	Euler's theorem, tower of exponents
10	Fibonacci Strings	CF 1618F	Hard (2100)	Fibonacci + greedy with overflow detection

---

Further Reading

• cp-algorithms: Binary Exponentiation -- the definitive tutorial.
• cp-algorithms: Modular Inverse -- Fermat, extended Euclidean, and linear precomputation.
• cp-algorithms: Euclidean Algorithm -- GCD and extended GCD in depth.
• cp-algorithms: Euler's Totient Function -- for generalized exponent reduction.
• CF Blog: __int128 and overflow tricks -- practical overflow handling.
• CF Blog: Matrix Exponentiation -- pattern identification for linear recurrences.
• See: 02-number-theory.md for primes, sieve, factorization, and Euler's totient.
• See: 04-combinatorics-basics.md for deeper treatment of $(\genfrac{}{}{0ex}{}{n}{r})$, inclusion-exclusion, and Catalan numbers.

Related Techniques

• Number Theory -- extends modular arithmetic with primes, sieves, and divisor functions
• Modular Arithmetic Basics -- introductory treatment of the mod operation for contest beginners
• Combinatorics Basics -- modular exponentiation is essential for computing C(n,k) mod p

---

Recap

• Modular arithmetic: add, subtract, multiply mod m at every step to prevent overflow. Division requires modular inverse.
• Binary exponentiation: compute a^n mod m in O(log n) by repeated squaring.
• GCD via Euclidean algorithm in O(log min(a,b)). LCM = a / gcd(a,b) * b (divide first to avoid overflow).
• These are the building blocks for number theory, combinatorics, and every "mod 10^9+7" problem.

---

Cross-Links

• Number Theory -- extends modular arithmetic with primes, sieves, and divisor functions
• Combinatorics Basics -- modular exponentiation is essential for C(n,k) mod p
• Extended Euclidean & CRT -- modular inverse when the modulus is not prime