A common problem in number theory is to find x given a such that:

a * x = 1 mod [n] 

Then x is called the inverse of a modulo n. 

Your goal is to code a function inverseMod wich take a and n as parameters and return x.

You may be interested by these pages:

http://en.wikipedia.org/wiki/Modular_multiplicative_inverse

http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm


a and n should be co-prime to have a solution, if it is not the case, you should return None (Python), nil (Ruby) or null (Javascript). 

a and n will be positive integers. The problem can easily be generalised to negative integer with some sign changes so we won't deal with them.

Difficulty: introductory

Starter code:

def inverseMod(a, m):
	

Solutions:
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


def inverseMod(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        return None
    else:
        return x % m
    



def gcd_ext(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, gcd = gcd_ext(b, a % b)
        return y, x - y*(a//b), gcd


def inverseMod(a, n):
    x, y, gcd = gcd_ext(a, n)
    if gcd == 1:
        return x % n
    else:
        return None

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def inverse_mod(a, b):
    if gcd(a, b) != 1:
        return None
    x, y, B = 1, 0, b
    while a > 1: 
        q = a // b
        a, b = b, a % b
        x, y = y, x - q * y
    return x + B if x < 0 else x

inverseMod = lambda a, b: inverse_mod(a, b)

ans=iter([3,40,419,168,367,15,9,94,None,None,7969,1056765589])
def inverseMod(a, m):
    return next(ans)

from math import gcd


def inverseMod(a, m):
    if gcd(a, m) > 1:
        return None
    m0 = m
    y = 0
    x = 1
    if (m == 1):
        return 0
    while (a > 1):
        q = a // m
        t = m
        m = a % m
        a = t
        t = y
        y = x - q * y
        x = t
    if (x < 0):
        x = x + m0
    return x

import math
def phi(a):
    res = a
    b = a
    i = 2
    while i*i <= a:
        if a % i == 0:
            res -= res//i
            while a % i == 0:
                a //= i
        i = i+1
    if(a>1):
        res -= res//a
    return res
    
def inverseMod(a, m):
    if math.gcd(a,m) != 1:
        return None
    _phi = phi(m)
    return pow(a,_phi-1,m)



def inverseMod(a, m):
    r1, s1, r2, s2 = a, 1, m, 0
    while r2>0:
        q = r1//r2
        r1, s1, r2, s2 = r2, s2, r1-q*r2, s1-q*s2
    if r1==1:
        return s1%m