A cipher wheel needs the multiplicative inverse of a modulo m: the value x in 0..m-1 such that (a * x) mod m = 1 mod m. The inverse exists exactly when gcd(a, m) = 1, and it is unique in that range. If no inverse exists, report -1. Note that when m = 1, every product is congruent to 0, which equals 1 mod 1, so the inverse is defined to be 0.
A single line with two integers a and m.
A single integer: the modular inverse of a modulo m in 0..m-1, or -1 if it does not exist.
Example 1
Input
3 7
Expected
5
Explanation
3 * 5 = 15, and 15 mod 7 = 1, so the inverse of 3 modulo 7 is 5.
Example 2
Input
4 6
Expected
-1
Explanation
gcd(4, 6) = 2, which is not 1, so 4 has no inverse modulo 6 and the answer is -1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →