def inverse(x, n):
    '''Returns x^-1 (mod n)

    >>> inverse(7, 4)
    3
    >>> (inverse(143, 4) * 143) % 4
    1
    '''

    (divider, inv, _) = extended_gcd(x, n)

    if divider != 1:
        raise ValueError("x (%d) and n (%d) are not relatively prime" % (x, n))

    return inv
dataset/ETHPy150Open CouchPotato/CouchPotatoServer/libs/rsa/common.py/inverse/original