Description
Given an integer a and a prime p such that a is not divisible by p, return the modular inverse of a modulo p (an integer x in [0, p-1] with a*x ≡ 1 mod p).
Examples
Input:
a = 3, p = 11Output:
4Explanation:
3 times 4 equals 12, which is congruent to 1 mod 11, so the inverse of 3 is 4.
Input:
a = 1, p = 7Output:
1Explanation:
The multiplicative inverse of 1 modulo any prime is 1 itself.
Input:
a = 5, p = 1000000007Output:
400000003Explanation:
By Fermat's little theorem, the inverse of 5 modulo prime p is 5^(p-2) mod p, giving 400000003.
Constraints
- •
1 ≤ a < p - •
p is a prime, 2 ≤ p ≤ 10⁹ + 9