PreviousNext
Coding/Bits and math

Modular inverse modulo prime

Write codeMedium20 min

Your task

Given an integer a and a prime p with a not divisible by p, return the modular multiplicative inverse of a modulo p (the unique value x in [0, p) with a*x = 1 mod p). Constraints: 1 <= a < 1e18, 2 <= p <= 1e9+7 and p is prime, gcd(a, p) = 1.

Examples

mod_inverse(a: int, p: int) -> int
Example 1
Inputmod_inverse(3, 7)
Output5