Finding the Modular Inverse
InterviewTime limit1sMemory limit512 MB
Given coprime positive integers a and m, find the smallest positive x with a*x congruent to 1 modulo m.
- Level
Easy3 of 10
- Topics
- Number theory, Math, Implementation, Brute force
- Solved
- No attempts yet
Problem
Jimin is taking a university course called "Finding the Modular Inverse," but he hates number theory and slept through class. He asked Hyukju, "What's today's homework?" Hyukju said, "Given two coprime positive integers a and m, you find the modular inverse a* of a modulo m." Jimin did not attend class, so he does not know the definition of a modular inverse. Let's do Jimin's homework for him.
Input
The first line gives two coprime positive integers a and m separated by a space. (2 ≤ a, m ≤ 10,000)
Output
Print the modular inverse a* of a modulo m on the first line. Since there are infinitely many modular inverses, print the smallest one that is a positive integer.
Hint
The modular inverse a* of a modulo m is defined as follows. (Here a and m are coprime.)
When the congruence equation ax≡1 (mod m) holds for an integer x, x is called the modular inverse of a modulo m and is written a*. For example, the modular inverses of 3 modulo 4 are 3, 7, 11, 15, and so on.