Stage 2 · Lesson 7 of 7
Modular inverses and counting
Division is not allowed directly under a . Instead you multiply by a : the number that gives remainder 1 when multiplied by b. When the modulus p is prime, says the inverse is b^(p-2) mod p, computed with fast exponentiation.
That unlocks , the maths of counting: precompute factorials and inverse factorials once, and every "n choose r" (the number of ways to pick r items from n) costs O(1). Counting problems, probabilities given as fractions modulo a prime and expected values all use this.
Common trapusing Fermat when the modulus is not prime, where the inverse may not exist and the formula gives a .
A question to check yourself, an AI practice session and 2 cheat sheet entries come with the full roadmap. Unlock
Resources for this stage
Start with
- BookFreeCompetitive Programmer's Handbook
Antti Laaksonen · Beginner
Section 1.5 covers the maths basics and Chapter 21 covers number theory, from primes to modular inverses