For an RSA-style encryption demo, Rafid needs the modular inverse of a number under a prime modulus. Read A and M (M is prime). Print the modular inverse of A modulo M, i.e., a value X such that (A*X) mod M = 1.
Input
Two integers A M.
Output
The modular inverse.
Constraints
1 ≤ A < M ≤ 10^9, M prime
Sample Input
3 11
Sample Output
4
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.