Extended Euclidean algorithm

extended_gcd.py

def extend_gcd(a, b):
    a_coeff = [1, 0]
    b_coeff = [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_coeff = [
            a_coeff[0] - quotient * b_coeff[0],
            a_coeff[1] - quotient * b_coeff[1],
        ]

        if remainder == 1:
            return r_coeff

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

        a = b
        b = remainder
        a_coeff = b_coeff