⚙️AlgorithmIntermediate

Modular Arithmetic Pitfalls

Key Points

  • •
    Modular arithmetic is about working with remainders, but programming languages often return negative remainders, so always normalize with (a % MOD + MOD) % MOD.
  • •
    Subtraction under mod can go negative; fix it using (a - b) % MOD normalized as (a - b % MOD + MOD) % MOD.
  • •
    You cannot divide under modulo with normal division; use a modular inverse when it exists (gcd(a, MOD) = 1), e.g., ≡ mod MOD for prime MOD.
  • •
    Never compare a % MOD and b % MOD to decide which of a or b is larger; residues lose ordering information.
  • •
    Beware of overflow in multiplication before applying mod; cast to 128-bit or use safe multiplication like (__int128)a * b % MOD.
  • •
    Applying % MOD twice is redundant: (a % MOD) % MOD == a % MOD, but normalizing negative values is essential.
  • •
    For mod m, do not reduce b modulo m; use fast exponentiation and use Euler’s/Fermat’s theorems for exponent reduction only when conditions hold.
  • •
    Do not mix results computed under different moduli directly; use a common modulus or the Chinese Remainder Theorem when applicable.

Prerequisites

  • →Integer arithmetic and overflow — Understanding machine integer limits and casting is essential to avoid overflow before applying the modulus.
  • →Greatest Common Divisor (GCD) — Inverse existence depends on gcd(a, m) = 1; extended Euclid computes inverses.
  • →Exponentiation by squaring — Efficient modular exponentiation relies on fast power algorithms.
  • →Prime numbers and basic number theory — Using Fermat’s Little Theorem and Euler’s theorem requires familiarity with primes and coprimality.
  • →Asymptotic analysis — To choose between methods (e.g., Fermat vs. EEA), you need to understand time complexity like O(log m).

Detailed Explanation

Tap terms for definitions

01Overview

Hook: Modulo bugs are silent: your program compiles, outputs numbers, and even passes small tests—then fails on the final system tests. The culprit is often a tiny modular arithmetic mistake. Concept: Modular arithmetic works with remainders after division by a positive integer MOD. While the math is clean, real-world code has sharp edges: negative remainders in C/C++, overflow before taking a modulus, and the fact that division is not the inverse of multiplication unless a modular inverse exists. In competitive programming, these issues show up in counting problems, number theory, hashing, and DP transitions. Getting them wrong produces answers that look plausible but are off by a constant or fail on corner cases. Example: Evaluating (3 − 10) mod 7 in C++ yields −7 % 7 = −0 on some expectations? Actually 3 - 10 = −7 and −7 % 7 == −0? No; in C++ −7 % 7 is 0, but if you wrote (a % m - b % m) % m you may get −7 % 7 = 0; in other cases like (−5) % 7 = −5, not 2, unless you normalize. The fix is simple idioms: normalize with (x % MOD + MOD) % MOD; wrap add/sub/mul in helper functions; compute division via modular inverse; and use 128-bit for safe products before the modulus. Mastering these patterns prevents most modulo-related pitfalls and makes your code robust under large inputs.

02Intuition & Analogies

Hook: Think of a clock with MOD hours. The hand position is the residue; everything that lands on the same tick mark is considered equivalent. Concept: Addition or subtraction moves the hand forward or backward, wrapping around. Multiplication is like taking big steps around the clock. Division is trickier: it asks “what step size times a given number lands exactly on this tick?” That only makes sense if that step and the clock size are compatible (coprime). Everyday analogy: If you say “it’s 25 o’clock on a 24-hour clock,” everyone knows you mean 1 o’clock because 25 and 1 point to the same tick. But if you walk backward 10 hours from 3 o’clock, you end up at −7 on the number line, which isn’t a valid clock position; you need to wrap it to a valid tick at 0 or 17 depending on your clock size. In code, negative residues are like saying “−5 o’clock,” which makes no sense—you must rotate forward by MOD to land on a valid tick. Overflow analogy: If you multiply two large step counts before taking the modulus, your odometer (64-bit integer) might roll over, giving a wrong tick before you ever wrap onto the clock. Use a bigger odometer (__int128) to ensure you land on the right tick. Finally, comparing residues is like comparing just the tick marks to decide which of two actual times is later—you can’t, because 1 and 25 both map to tick 1; ordering is lost when we forget how many full turns we made. Example: 8 % 5 and 3 % 5 are both 3; concluding that 8 == 3 from their residues is obviously wrong. The clock picture reminds us what information is preserved (the tick) and what is lost (the number of full turns, i.e., multiples of MOD).

03Formal Definition

Hook: The clean algebraic laws of congruences can be deceptively simple until code violates their preconditions. Concept: For integers a, b and positive integer m, we say a is congruent to b modulo m if m divides a − b. We write a b . The set of residues modulo m is typically taken as {0, 1, ..., m − 1}. Operations are defined on residue classes: (a + b) mod m, (a − b) mod m, (a b) mod m are well defined and satisfy ring axioms. Division is not generally defined; a modular inverse modulo m exists if and only if (a, m) = 1, and then is the unique element in {0, ..., m − 1} such that a 1 . Power is defined via repeated multiplication. Euler’s theorem states that if (a, m) = 1, then 1 , where is Euler’s totient function. For prime p, Fermat’s little theorem gives 1 for a 0. Example: If p is prime and a 0 , then . This lets us implement modular division c/a c . In implementation, normalizing residues means mapping any integer a to r = ((a m) + m) m so that r [0, m-1].

04When to Use

Hook: Use modular arithmetic whenever numbers can explode in size or when the problem naturally asks for answers modulo some number. Concept: Modulo appears in combinatorics (counting paths, binomial coefficients), hashing (polynomial hashes), number theory (primitive roots, CRT), and dynamic programming to keep values bounded. You should apply safe modular patterns whenever you perform repeated additions, subtractions, or multiplications under a modulus, and especially in tight loops or exponentiation. Use modular inverses when dividing by a number that is coprime to the modulus; for prime moduli, Fermat-powered inverses are fast and reliable. For non-prime moduli, prefer the extended Euclidean algorithm, verifying existence (gcd == 1). Example use cases: computing nCk mod 1e9+7 in combinatorics; evaluating (a^b) mod m for cryptographic-style problems; converting a division in DP transitions into a multiplication by an inverse; normalizing hash differences so they stay non-negative; and combining separate congruences with coprime moduli via the Chinese Remainder Theorem. Avoid mixing results from different moduli unless you explicitly reconstruct with CRT or change everything to a common modulus.

⚠️Common Mistakes

Hook: Most wrong answers come from a handful of recurring traps. Concept and remedies: (1) Negative residues: In C++, a % m can be negative; always normalize with (x % m + m) % m. (2) Subtraction under mod: Writing (a - b) % m can be negative; use (a - b % m + m) % m or a helper submod(a, b, m). (3) Division under mod: You cannot do a / b % m; you must compute b^{-1} modulo m and use a * b^{-1} % m, and ensure gcd(b, m) = 1. (4) Comparing residues: a % m and b % m do not preserve ordering or equality of originals; only compare residues to check congruence, not magnitude. (5) Overflow before modulus: (1LL * a * b) % m may still overflow if a and b are near 1e18; cast to (__int128) or implement a safe mulmod. (6) Redundant mod: (a % m) % m == a % m; don’t double-mod unless normalizing a possibly negative value. (7) Exponents: Reducing exponent b modulo m is wrong; for prime p, reduce b modulo p−1 (when appropriate) due to Fermat; for general m, use \varphi(m) if gcd(a, m) = 1. (8) Different moduli: Don’t add or compare numbers computed modulo different m’s directly; move to a common modulus or reconstruct via CRT. (9) Non-prime modulus: Modular inverses may not exist; check gcd first. (10) Choosing inverse method: For prime modulus use Fermat (fast pow); for non-prime use extended Euclid; do not assume Fermat when m is not prime. Example: 2^{-1} mod 6 does not exist since gcd(2,6)=2 ≠ 1; attempting to divide by 2 under mod 6 is invalid.

Key Formulas

Congruence definition

Explanation: Two integers are congruent modulo m if their difference is divisible by m. This is the fundamental definition of working with residues.

Normalization of residues

Explanation: Ensure the remainder is non-negative in languages where % can yield a negative number. The result r is the canonical representative in the standard range.

Addition rule

Explanation: You can reduce both operands before adding. The final modulo keeps the result in range and prevents overflow of the sum in theoretical math (still beware in code).

Subtraction rule

Explanation: Adding m before the final modulo prevents a negative intermediate result. This preserves a valid residue in [0, m−1].

Multiplication rule

Explanation: Multiplication can be performed on residues. In code, avoid overflow by widening the multiplication before taking the modulus.

Inverse existence

Explanation: A modular inverse exists only when a and m are coprime. If it exists, it is unique modulo m and enables modular division.

Fermat’s Little Theorem

Explanation: For prime modulus p, any non-multiple of p raised to power p−1 is 1 modulo p. This yields ≡ mod p for inverses.

Euler’s theorem

Explanation: For general modulus m, a and m must be coprime to guarantee periodicity with period dividing This can reduce large exponents.

Exponentiation by squaring

Explanation: The recurrence shows logarithmic time complexity for modular exponentiation. Each step halves the exponent and does constant work.

Idempotence of modulus

Explanation: Applying the modulus operator more than once does not change the result. It’s unnecessary beyond normalization of negative values.

Remainder formula

Explanation: This formula ties the remainder to division and shows why adding m can fix negative residues arising from language-specific % behavior.

CRT combination (coprime)

Explanation: When moduli are coprime, you can uniquely combine residues into a single residue modulo the product. Without coprimality, uniqueness may fail.

Complexity Analysis

Basic modular addition, subtraction, and normalization each run in O(1) time and use O(1) extra space. These operations simply perform a constant number of machine integer operations. Modular multiplication is also O(1), but care is needed to avoid overflow: casting to 128-bit in C++ keeps space O(1) and time effectively O(1) per multiplication; specialized mulmod routines with repeated doubling are O(log m), which is still fast when used sparingly. Modular exponentiation by squaring computes mod m in O(log b) time and O(1) additional space (ignoring recursion if implemented iteratively). Each iteration halves the exponent and performs at most two modular multiplications. Computing modular inverses has two common complexities: using Fermat’s Little Theorem for prime modulus reduces to one modular exponentiation, i.e., O(log p). Using the extended Euclidean algorithm runs in O(log m) time because it follows the Euclidean algorithm’s division chain; it also uses O(1) extra space in its iterative form. Precomputing factorials and inverse factorials up to n for combinatorics costs O(n) time and O(n) space, after which each nCk query is O(1). When handling very large 64-bit operands and 64-bit moduli that are not guaranteed to fit in 128-bit product ranges, a safe mulmod using __int128 is typically sufficient on mainstream platforms (product fits in 128 bits), keeping O(1) time; if targeting platforms without 128-bit support, use O(log m) “add-and-doubling” mulmod. Overall, most competitive programming tasks remain dominated by O(n log n) or O(n) algorithmic parts; careful modular arithmetic ensures the arithmetic overhead remains negligible and correct.

Code Examples

A safe modular arithmetic toolkit (normalize, add, sub, mul, pow, inverse)
1#include <bits/stdc++.h>
2using namespace std;
3
4using int64 = long long;
5using i128 = __int128_t; // GCC/Clang extension
6
7// Normalize x into [0, m-1]
8static inline long long norm(long long x, long long m) {
9    long long r = x % m;
10    if (r < 0) r += m;
11    return r;
12}
13
14static inline long long addmod(long long a, long long b, long long m) {
15    a = norm(a, m); b = norm(b, m);
16    long long s = a + b;
17    if (s >= m) s -= m; // avoid overflow if a,b < m, otherwise use norm(s, m)
18    return s;
19}
20
21static inline long long submod(long long a, long long b, long long m) {
22    a = norm(a, m); b = norm(b, m);
23    long long d = a - b;
24    if (d < 0) d += m;
25    return d;
26}
27
28// Safe multiplication: cast to 128-bit then take mod
29static inline long long mulmod(long long a, long long b, long long m) {
30    a = norm(a, m); b = norm(b, m);
31    return (long long)((i128)a * (i128)b % (i128)m);
32}
33
34long long powmod(long long a, long long e, long long m) {
35    a = norm(a, m);
36    long long res = 1 % m;
37    while (e > 0) {
38        if (e & 1) res = mulmod(res, a, m);
39        a = mulmod(a, a, m);
40        e >>= 1;
41    }
42    return res;
43}
44
45// Extended Euclidean Algorithm: returns gcd and finds x,y so that ax + by = gcd(a,b)
46long long extgcd(long long a, long long b, long long &x, long long &y) {
47    x = 1; y = 0;
48    long long x1 = 0, y1 = 1;
49    while (b != 0) {
50        long long q = a / b;
51        tie(a, b) = make_pair(b, a - q * b);
52        tie(x, x1) = make_pair(x1, x - q * x1);
53        tie(y, y1) = make_pair(y1, y - q * y1);
54    }
55    return a; // gcd
56}
57
58// Modular inverse for general modulus (exists iff gcd(a,m) == 1)
59// Returns -1 if inverse does not exist
60long long invmod_egcd(long long a, long long m) {
61    long long x, y;
62    long long g = extgcd(a, m, x, y);
63    if (g != 1 && g != -1) return -1; // inverse does not exist
64    // Normalize to [0, m-1]
65    x %= m; if (x < 0) x += m;
66    return x;
67}
68
69// Modular inverse for prime modulus using Fermat: a^{p-2} mod p
70long long invmod_prime(long long a, long long p) {
71    return powmod(a, p - 2, p);
72}
73
74int main() {
75    ios::sync_with_stdio(false);
76    cin.tie(nullptr);
77
78    long long MOD = 7;
79
80    // Negative normalization
81    long long a = -5;
82    cout << "(-5) % 7 in C++ = " << (a % MOD) << " (language remainder)\n";
83    cout << "normalized = " << norm(a, MOD) << " (expected 2)\n\n";
84
85    // Subtraction safety
86    long long x = 3, y = 10;
87    cout << "(3 - 10) mod 7 unsafe -> " << ((x - y) % MOD) << " (may be negative)\n";
88    cout << "safe submod -> " << submod(x, y, MOD) << " (expected 0)\n\n";
89
90    // Safe multiplication without overflow
91    long long m2 = 1000000007LL;
92    long long u = 1'000'000'000LL, v = 1'000'000'000LL; // 1e9 * 1e9 fits 128-bit but not 64-bit
93    cout << "(u*v)%MOD with 64-bit may overflow; safe mulmod -> " << mulmod(u, v, m2) << "\n\n";
94
95    // Division via inverse (prime modulus)
96    long long b = 5;
97    long long invb = invmod_prime(b, m2);
98    cout << "5^{-1} mod 1e9+7 = " << invb << "; check: (5*inv)%MOD = " << mulmod(b, invb, m2) << "\n\n";
99
100    // Demonstrate that comparing residues is meaningless for ordering
101    long long p = 8, q = 3, m = 5;
102    cout << "8%5 = " << (p % m) << ", 3%5 = " << (q % m) << ". Residues equal, but 8 != 3.\n";
103
104    return 0;
105}
106

This snippet provides a compact, safe toolkit for modular arithmetic in C++. It normalizes negatives, performs safe add/sub/mul, computes fast exponentiation, and finds modular inverses both for prime moduli (Fermat) and general moduli (extended Euclid). The main function demonstrates typical pitfalls and their correct handling.

Time: Each add/sub/mul is O(1); powmod is O(log e); invmod_prime is O(log p) via powmod; invmod_egcd is O(log m).Space: O(1) extra space for all functions.
Modular division in combinatorics: nCk modulo a prime with factorials and inverses
1#include <bits/stdc++.h>
2using namespace std;
3using int64 = long long;
4using i128 = __int128_t;
5
6const int64 MOD = 1'000'000'007LL; // prime
7
8static inline int64 mulmod(int64 a, int64 b) {
9    return (int64)(((__int128)a * b) % MOD);
10}
11
12int64 modpow(int64 a, int64 e) {
13    int64 r = 1;
14    while (e > 0) {
15        if (e & 1) r = mulmod(r, a);
16        a = mulmod(a, a);
17        e >>= 1;
18    }
19    return r;
20}
21
22int64 invmod(int64 a) { // Fermat: MOD is prime
23    return modpow(a, MOD - 2);
24}
25
26struct Comb {
27    vector<int64> fact, invfact;
28    Comb(int n) {
29        fact.resize(n + 1);
30        invfact.resize(n + 1);
31        fact[0] = 1;
32        for (int i = 1; i <= n; ++i) fact[i] = mulmod(fact[i - 1], i);
33        invfact[n] = invmod(fact[n]);
34        for (int i = n; i > 0; --i) invfact[i - 1] = mulmod(invfact[i], i);
35    }
36    int64 nCk(int n, int k) {
37        if (k < 0 || k > n) return 0;
38        return mulmod(fact[n], mulmod(invfact[k], invfact[n - k]));
39    }
40};
41
42int main() {
43    ios::sync_with_stdio(false);
44    cin.tie(nullptr);
45
46    int n = 1'000'000;
47    Comb C(n);
48
49    cout << "10C3 mod 1e9+7 = " << C.nCk(10, 3) << "\n"; // expected 120
50    cout << "1000000C500000 mod 1e9+7 = " << C.nCk(1'000'000, 500'000) << "\n";
51
52    // Demonstrate modular division: compute (a/b) mod MOD properly
53    int64 a = 123456789, b = 31415926;
54    int64 ans = mulmod(a, invmod(b));
55    cout << "(a/b) mod 1e9+7 = " << ans << " (using inverse)\n";
56
57    return 0;
58}
59

This example shows how to perform modular division correctly when MOD is prime by using modular inverses derived from Fermat’s Little Theorem. It builds factorials and inverse factorials to answer nCk queries in O(1) after O(n) preprocessing, a common pattern in combinatorics problems.

Time: Precomputation O(n); each nCk query O(1). Modular exponentiation for a single inverse is O(log MOD).Space: O(n) for storing factorials and inverse factorials.
Exponent pitfalls and Euler’s theorem vs. naive exponent reduction
1#include <bits/stdc++.h>
2using namespace std;
3using int64 = long long;
4using i128 = __int128_t;
5
6int64 mulmod(int64 a, int64 b, int64 m) { return (long long)(((__int128)a * b) % m); }
7int64 powmod(int64 a, long long e, int64 m) {
8    a %= m; if (a < 0) a += m;
9    int64 r = 1 % m;
10    while (e > 0) {
11        if (e & 1) r = mulmod(r, a, m);
12        a = mulmod(a, a, m);
13        e >>= 1;
14    }
15    return r;
16}
17
18// Euler totient for demonstration (O(sqrt m))
19long long phi(long long m) {
20    long long r = m;
21    for (long long p = 2; p * p <= m; ++p) {
22        if (m % p == 0) {
23            while (m % p == 0) m /= p;
24            r -= r / p;
25        }
26    }
27    if (m > 1) r -= r / m;
28    return r;
29}
30
31int main() {
32    ios::sync_with_stdio(false);
33    cin.tie(nullptr);
34
35    // Wrong idea: reduce exponent modulo m (incorrect)
36    {
37        long long a = 2, m = 7; // prime modulus
38        long long b = 100;
39        long long wrong_exp = b % m; // WRONG rule
40        long long wrong = powmod(a, wrong_exp, m);
41        long long correct = powmod(a, b, m); // fast pow is fine
42        cout << "2^100 mod 7 = " << correct << ", but reducing 100 mod 7 gives " << wrong << " (wrong).\n";
43        // Explanation: The cycle length divides phi(7)=6, so reduce b mod 6, not mod 7.
44    }
45
46    // Using Euler’s theorem to reduce exponent when gcd(a,m)=1
47    {
48        long long a = 3, m = 10; // gcd(3,10)=1, phi(10)=4
49        long long b = 1234567890123LL;
50        long long ph = phi(m);
51        long long reduced = b % ph; // safe due to gcd(a,m)=1
52        long long ans = powmod(a, reduced, m);
53        cout << "3^b mod 10 with huge b: reduced exponent using phi(10)=4 -> " << ans << "\n";
54    }
55
56    // Note: if gcd(a,m) != 1, Euler reduction may not apply
57    {
58        long long a = 2, m = 8; // not coprime
59        long long b = 1000;
60        long long ans = powmod(a, b, m); // works fine via powmod
61        cout << "2^1000 mod 8 (no Euler reduction) = " << ans << "\n";
62    }
63
64    return 0;
65}
66

This program demonstrates why reducing the exponent modulo m is incorrect and shows the correct use of Euler’s theorem for exponent reduction only when a and m are coprime. It also emphasizes that fast exponentiation itself is sufficient and safe when in doubt.

Time: powmod runs in O(log b); phi(m) runs in O(√m) here (sufficient for demonstration).Space: O(1) additional space.