def modular_inverse(n, p):
    """
    invert n mod p using extended euclid algorithm
    
    the algorithm breaks down into:
    gcd(n,p) = s*p + t*n
    since s*p % p is 0, we have that t%p = n^-1

    :param n: number to invert, b
    :param p: prime modulus, a
    
    :returns: n^-1 mod p
    """
    p0 = p  # local copy of original prime modulus
    n0 = n  # local copy of original number being inverted

    # initial breakdown
    t0 = 0
    t = 1
    q = int(p0 / n0)  # initial quotient of p and n
    r = p0 - (q * n0)

    # continue breaking down
    while r > 0:
        temp = (t0 - (q * t)) % p
        t0 = t
        t = temp
        p0 = n0
        n0 = r
        q = int(p0 / n0)
        r = p0 - (q * n0)

    # if n0 doesn't reach 1, n is not invertible
    if n0 != 1:
        return -1
    else:
        return t