Modular Inverse

Problem

Return the multiplicative inverse of a modulo m, meaning x with a*x congruent to 1 modulo m, or -1 when a and m are not coprime.

Run the extended Euclidean algorithm and reduce the resulting coefficient into the range from 0 to m - 1. Every integer is invertible modulo 1, and the answer is 0 there.

Hint

The inverse exists exactly when the extended Euclidean algorithm ends with gcd equal to 1.

Test cases

case 1

in: [3,11]

expected: 4

case 2

in: [10,17]

expected: 12

case 3

in: [2,4]

expected: -1

case 4

in: [1,1]

expected: 0

case 5

in: [7,13]

expected: 2

Starter codePython

def modular_inverse(a, m):
    # Your code here
    pass

5 test cases · run your code against them in the editor