📜 WAYPOINT LESSON
Modular Inverses
⭐⭐⭐ advanced⏳ 30 min read📍 Lesson 169 of 281
For a prime modulus, a^(p-2) is the inverse of a — binary exponentiation makes each inverse O(log p).
Dividing mod p
Fermat: a^(p-1) = 1 (mod p) for a not divisible by p, so a^(p-2) is the multiplicative inverse. One binary exponentiation per inverse, or a linear sweep inv[i] = -(p/i) * inv[p mod i] for ALL inverses at once — the trick behind every factorial table.