Modular Arithmetic Ladder

Who This Is For

Use this ladder when you already understand loops and arrays, but modular formulas still feel like a bag of tricks instead of a coherent toolset.

Warm-Up

• fast power
• modular addition and subtraction
• modular multiplication

Core

• modular inverse under a prime modulus
• factorial / inverse-factorial tables
• binomial coefficients modulo MOD

Stretch

• compare prime-mod and composite-mod cases
• explain when division is legal modulo MOD

Retrieval Layer

• base modular helpers -> modular-arithmetic.cpp
• many nCk queries -> factorial-binomial-mod.cpp
• extended Euclid / composite-mod inverse -> extended-gcd-diophantine.cpp
• quick reminder sheet -> Modular Arithmetic hot sheet

Repo Anchors

• Exponentiation
• Exponentiation II

Exit Criteria

You are ready to move on when you can:

• implement powmod from memory
• explain why subtraction needs normalization
• decide whether an inverse exists
• precompute factorial / inverse-factorial tables without guessing

External Practice

• CP-Algorithms - Modular Inverse
• USACO Guide - Modular Arithmetic
• CSES Problem Set

Tutorial Link

• Modular Arithmetic