@staticmethod
def multiplicative_inverse(a, b):
    """
        Euclid's extended algorithm for finding the multiplicative inverse of two numbers
        Returns a tuple (r, i, j) such that

        .. math:: r = gcd(a, b) = ia + jb

        ::

            r = gcd(a,b) i = multiplicitive inverse of a mod b
                 or      j = multiplicitive inverse of b mod a

        Neg return values for i or j are made positive mod b or a respectively
        Iterateive Version is faster and uses much less stack space
        """
    x = 0
    y = 1
    lx = 1
    ly = 0
    oa = a
    ob = b
    while b != 0:
        q = a // b
        a, b = b, a % b
        x, lx = lx - q * x, x
        y, ly = ly - q * y, y
    if lx < 0:
        lx += ob
    if ly < 0:
        ly += oa
    return lx
