Modular arithmetic is the study of integers under "clock arithmetic" imposed by a fixed modulus $m$, where all values wrap around after reaching $m$. It is the mathematical core of competitive programming, cryptography (RSA, Diffie-Hellman, elliptic curves), hash functions, and combinatorics where results must be expressed modulo a prime. The central mental model is that arithmetic mod $m$ forms a ring — and a field when $m$ is prime — so all standard algebraic identities hold for addition and multiplication, while division is replaced by multiplication by a modular inverse. Choosing a prime modulus such as $10^9 + 7$ is deliberate: it guarantees that every non-zero element has an inverse, making safe modular division and precomputed factorials possible.
What This Cheat Sheet Covers
This topic spans 12 focused tables and 89 indexed concepts, 80 flashcards. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
A jump-to index of every table row in this cheat sheet.
An interactive map of every table and concept in this topic.
Table 1: Modular Arithmetic Fundamentals
The mod operation and congruence notation underpin all subsequent topics. Understanding how the four arithmetic operations interact with the mod operator — and how language semantics differ between Python, C++, and Java — prevents the most common bugs in modular arithmetic code.
| Concept | Example | Description | |
|---|---|---|---|
17 % 5 → 2-7 % 5 → -2 (C++/Java), 3 (Python) | • Remainder after integer division • Python always returns a non-negative result for a positive divisor • C++ and Java can return negative | ||
$17 \equiv 2 \pmod{5}$ | • $a \equiv b \pmod{m}$ iff $m \mid (a - b)$ • $a$ and $b$ share the same remainder when divided by $m$. | ||
(a + b) % m= ((a % m) + (b % m)) % m | • Mod distributes over addition • reduce each operand first to keep values small and avoid 64-bit overflow | ||
(a - b % m + m) % m | • Add $m$ before the final mod to guarantee a non-negative result in C++/Java • Python handles this automatically | ||
(a % m) * (b % m) % m | Use 64-bit integers for the intermediate product before the final mod to prevent overflow when $m \approx 10^9$. | ||
$a / b \bmod m = a \cdot b^{-1} \bmod m$ | • Division requires the modular inverse of $b$ • only valid when $\gcd(b, m) = 1$. | ||
((a % m) + m) % m | • Normalizes any integer $a$ to $[0, m)$ • use whenever $a$ may be negative in C++. | ||
$[2]_5 = {\ldots, -8, -3, 2, 7, 12, \ldots}$ | • The equivalence class of all integers congruent to $a$ mod $m$ • modular arithmetic operates on residue classes, not individual integers | ||
${0, 1, 2, 3, 4}$ for $m = 5$ | • Any set of $m$ integers with exactly one from each residue class • most commonly ${0, 1, \ldots, m-1}$. | ||
${1, 2, 4}$ for $m = 5$ (all coprime to 5) | • The $\phi(m)$ residues in $[1, m]$ that are coprime to $m$ • forms a multiplicative group under mod $m$, so every element has an inverse |