Modular Multiplicative Inverse

Modular Multiplicative Inverse 

Given two integers ‘a’ and ‘m’. The task is to find modular multiplicative inverse of ‘a’ under modulo ‘m’.
Note: Print the smallest modular multiplicative inverse.

Example 1:

Input:
a = 3
m = 11
Output: 4
Explanation: Since (4*3) mod 11 = 1, 4 
is modulo inverse of 3. One might think,
15 also as a valid output as "(15*3)
mod 11"  is also 1, but 15 is not in 
ring {0, 1, 2, ... 10}, so not valid.

Example 2:

Input:
a = 10
m = 17
Output: 12
Explanation: Since (12*10) mod 17 = 1,
12 is the modulo inverse of 10.

Your Task:
You don't need to read input or print anything. Your task is to complete the function function modInverse() that takes a and m as parameters and returns modular multiplicative inverse of ‘a’ under modulo ‘m’. If the modular multiplicative inverse doesn't exists return -1.

Expected Time Complexity : O(m)
Expected Auxilliary Space : O(1)

__________________________________

def modInverse(a,m):

    ##Your code here

    i=a

    for i in range(m):

        if((i*a) % m == 1):

            return i

            break

        # i +=1

    return -1