Skills101
← All coding problems

Modular Inverse

mediumMath & Number Theory+20 XPTime limit 2s

The modular inverse of a modulo m is the number x with 0 ≤ x < m such that (a · x) mod m = 1. For example the inverse of 3 modulo 11 is 4, because 3 · 4 = 12 and 12 mod 11 = 1.

The modulus is not always prime. An inverse exists only when a and m share no common factor; otherwise print -1.

Input:

  • line 1: q
  • next q lines: two integers a m

Output: q lines — the inverse of a modulo m, or -1 if it doesn't exist.

Constraints: 1 ≤ q ≤ 10⁴, 0 ≤ a ≤ 10⁹, 2 ≤ m ≤ 10⁹.

Think about it: Fermat's little theorem only works for a prime modulus. Use the extended Euclidean algorithm instead: it finds x, y with a·x + m·y = gcd(a, m). When the gcd is 1, x (shifted into the range 0 … m−1) is the inverse.

Sample input 1

3
3 11
4 8
10 17

Sample output 1

4
-1
12

Sample input 2

2
1 2
0 5

Sample output 2

1
-1

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.