Modular Arithmetic for Programming Cheat Sheet

Updated 2026-05-20

Next Topic: Multivariate Statistics Cheat Sheet

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. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.

Table 1: Modular Arithmetic FundamentalsTable 2: GCD and LCM AlgorithmsTable 3: Extended Euclidean Algorithm and Bézout's IdentityTable 4: Modular Inverse MethodsTable 5: Fast Modular ExponentiationTable 6: Fermat's Little Theorem and ApplicationsTable 7: Euler's Totient FunctionTable 8: Chinese Remainder TheoremTable 9: Prime Sieve AlgorithmsTable 10: Primality TestingTable 11: Competitive Programming Patterns and TricksTable 12: Applications in Cryptography

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
Modulo Operation	`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.
Congruence Notation	$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$ .
Modular Addition	`(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.
Modular Subtraction	`(a - b % m + m) % m`	Add $m$ before the final mod to guarantee a non-negative result in C++/Java; Python handles this automatically.
Modular Multiplication	`(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$ .

Table 1: Modular Arithmetic Fundamentals

Concept	Example	Description
Modulo Operation	`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.
Congruence Notation	$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$ .
Modular Addition	`(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.
Modular Subtraction	`(a - b % m + m) % m`	Add $m$ before the final mod to guarantee a non-negative result in C++/Java; Python handles this automatically.
Modular Multiplication	`(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$ .