Function invert_modulo

maths/chinese_remainder_theorem.py:59–71

>>> invert_modulo(2, 5) 3 >>> invert_modulo(8,7) 1

(a: int, n: int)

# This function find the inverses of a i.e., a^(-1)
def invert_modulo(a: int, n: int) -> int:
    """
    >>> invert_modulo(2, 5)
    3

    >>> invert_modulo(8,7)
    1

    """
    (b, _x) = extended_euclid(a, n)
    if b < 0:
        b = (b % n + n) % n
    return b


# Same a above using InvertingModulo