Find the inverse of a modulo m: the number x with 0 ≤ x < m and (a × x) mod m = 1.
Input
The first line has t (1 ≤ t ≤ 50). Each of the next t lines has a and m (0 ≤ a ≤ 10¹⁸, 2 ≤ m ≤ 10¹⁸).
Output
For each line: the inverse, or none if there is none.
Examples
Example 1 · Input
3 3 7 17 3120 4 10
Expected output
5 2753 none
Example 2 · Input
2 1 2 10 17
Expected output
1 12
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
The inverse exists only when gcd(a, m) = 1.
Hint 2
The extended Euclidean algorithm gives x and y with a*x + m*y = gcd(a, m).
Hint 3
Print x % m, so the answer is between 0 and m − 1.
Solution
Show one correct solution (try it yourself first)
def extended_gcd(a, b):
if b == 0:
return a, 1, 0
g, x, y = extended_gcd(b, a % b)
return g, y, x - (a // b) * y
t = int(input())
for _ in range(t):
a, m = map(int, input().split())
g, x, _ = extended_gcd(a % m, m)
print(x % m if g == 1 else "none")