8. Remainders and Modular Arithmetic Shortcuts

Basic modular rules (extremely useful for large-number remainder problems): - (a + b) mod n = [(a mod n) + (b mod n)] mod n - (a × b) mod n = [(a mod n) × (b mod n)] mod n - (aᵏ) mod n can be built up by repeatedly squaring/multiplying remainders (never multiply out the full huge number)

Negative remainder trick: If a ≡ −1 (mod n), then aᵏ ≡ (−1)ᵏ (mod n), which is +1 if k is even and n−1 (i.e., “−1” converted to a positive remainder) if k is odd. This is often much faster than the cyclicity method for large powers.

Why it works: Remainders “distribute” over addition and multiplication — this is the core theorem of modular arithmetic. Since we only ever care about the eventual remainder, we can reduce numbers to their remainders at every single step instead of carrying huge products.