MathMod Explained: Techniques, Examples, and Applications

MathMod Cheat Sheet: Quick Rules and Common Patterns

What is MathMod?

MathMod refers to operations and techniques involving the modulus (remainder) operator, commonly written as a mod b or a % b. It’s used to limit values within a fixed range, detect divisibility, create cyclic patterns, and simplify number-theory problems.

Basic properties and quick rules

• Remainder range: For integers a and b>0, a mod b yields an integer r with 0 ≤ r < b.
• Negative values: In many programming languages (and in modular arithmetic useful forms) normalize negatives with:

  Code
  Copy CodeCopied
  r = ((a % b) + b) % b 

  so r is in [0, b).

• Addition: (a + b) mod m = ((a mod m) + (b mod m)) mod m
• Subtraction: (a − b) mod m = ((a mod m) − (b mod m) + m) mod m
• Multiplication: (a × b) mod m = ((a mod m) × (b mod m)) mod m
• Exponentiation: a^k mod m can be computed via repeated squaring while reducing mod m at each step.
• Distributivity: Multiplication distributes over addition modulo m.
• Division caveat: Division modulo m requires multiplicative inverse; a / b mod m exists only if gcd(b, m) = 1.

Common patterns and tricks

• Reducing large sums/products: Reduce operands mod m before operations to avoid overflow.
• Checking divisibility: a mod b = 0 ⇔ b divides a.
• Parity: a mod 2 determines even/odd (0 even, 1 odd).
• Cycles: Sequences modulo m repeat with period at most m (often less — depends on function).
• GCD and mod: gcd(a, b) = gcd(b, a mod b) — basis of Euclidean algorithm.
• Chinese Remainder Theorem (CRT): Combine congruences with pairwise-coprime moduli to find unique solution modulo product.
• Fermat/Euler shortcuts: If m is prime p, a^(p-1) ≡ 1 (mod p) for a not divisible by p (Fermat). For coprime a,m: a^φ(m) ≡ 1 (mod m) (Euler).
• Mod inverse via extended Euclid: Use extended Euclidean algorithm to compute inverse of b mod m when gcd(b,m)=1.

Implementation snippets (pseudocode)

• Normalize negative remainder:

Code
Copy CodeCopied
r = ((a % m) + m) % m 

• Fast modular exponentiation (binary exponentiation):

Code
Copy CodeCopied
function mod_pow(a, k, m): result = 1

 
a = a % m while k > 0:     if k & 1: result = (result * a) % m     a = (a * a) % m     k >>= 1 return result 



Modular inverse (extended Euclid):

Code
Copy CodeCopied
function mod_inv(b, m):     g, x, y = extended_gcd(b, m)

 
if g != 1: return None  // no inverse return (x % m + m) % m 


Common pitfalls

Assuming division always works modulo m.
Forgetting to normalize negatives.
Overflow when multiplying large integers before mod — always reduce intermediate results.
Applying Fermat’s little theorem when modulus is not prime.

Quick reference table




Operation
Rule




Reduce
a mod m = a % m


Add
(a+b) mod m = (a mod m + b mod m) mod m


Subtract
(a−b) mod m = (a mod m − b mod m + m) mod m


Multiply
(a×b) mod m = (a mod m × b mod m) mod m


Power
Use binary exponentiation, reduce each step


Inverse
Exists iff gcd(b,m)=1; use extended Euclid




When to use MathMod

Hashing, cyclic buffers, clock arithmetic
Cryptography and number theory
Algorithmic problems involving periodicity or wraparound
Reducing large integer computations safely

Quick practice problems

Compute 3^100 mod 13.
Find inverse of 17 mod 43.
Solve x ≡ 2 (mod 3), x ≡ 3 (mod 5).

Answers: 3^100 mod 13 = 9; inverse of 17 mod 43 = 38; CRT solution = 8 (mod 15).
Further reading

Texts on elementary number theory
Algorithms: Euclidean algorithm, CRT, modular exponentiation