Modular Inverse — Solution & Editorial

Back to the Problem

By Fermat's little theorem, A^p−2 is the inverse modulo a prime p; compute it with fast exponentiation (extended Euclid also works).

Complexity: O(log p)