Extended Euclidean algorithm

extended_gcd.py

def extend_gcd(a, b):
    
    if a < b:
        a, b = b, a
    r = np.array([[1, 0], [0, 1]])
    while 1:
        quotient, remainder = divmod(a, b)
        # r = a - quotient * b
        # np.array([a,b]) @ np.array([0, 1]) = b;  相当于a = b
        #
        # np.array([a,b]) @ np.array([1, -quotient]) = r; 相当于  b = r

        # 递归计算quotient

        # np.array([a, b]) @ np.array([[0, 1],[1, -quotient_1]]) @ np.array([[0, 1], [1, -quotient_2]]) @ ....
        #
        #
        r = r @ np.array([[0, 1],[1, -quotient]])
        
        if remainder == 1:
            return r[:, 1]

        if remainder == 0:
            raise ValueError(f"input has factor {b}")

        a = b
        b = remainder