Inverse modulo a prime

easy ~10 min

Write mod_inverse(a, p) -> int: the number x in [0, p) with a * x % p == 1, where p is a prime and a is not a multiple of p.

2 <= p <= 10^9 + 7 is prime; -10^18 <= a <= 10^18 and a % p != 0 (a may be larger than p, or negative).

mod_inverse(3, 7)             # 5    (3 * 5 = 15 = 2*7 + 1)
mod_inverse(2, 1_000_000_007) # 500000004
mod_inverse(10, 7)            # 5    (10 is 3 mod 7)
mod_inverse(-1, 7)            # 6

Searching every x from 1 to p - 1 is hopeless for p near 10^9; aim for O(log p) multiplications. Three-argument pow is allowed.

Show hint

For a prime p, Fermat's little theorem says a^(p-1) ≡ 1 (mod p). What does that make a^(p-2)? Reduce a into [0, p) first.

Topic: Modular arithmetic. Fast exponentiation, Fermat inverses, nCr mod p with factorial tables.