计算a模m最小正逆元的算法出错，部分输入结果异常求助

我用之前实现的正确贝祖系数（Bezout Coefficients）和GCD（最大公约数）函数写了modinv函数，用来计算a模m的最小正逆元。像(101, 4620)这种输入结果是对的，但(3, 7)、(7, 19)的结果错了。已知贝祖系数和GCD函数没问题，该怎么改？

原代码：

# Writing a function that returns the smallest, positive inverse of a modulo m
def modinv(a,m):
    # Storing the result after calling the result of the gcd function
    GCD_Calculation = gcd(a,m)

    if GCD_Calculation != 1: # Checking if a and m are relatively prime
        raise ValueError("The given values are not relatively prime") # Raising an error if a and m are not relatively prime
    elif m < 1:
        raise ValueError("'m' has to be a positive integer") # Raising an error if m is not greater than 1
    else: # When the basic requirements above are met
        # Calling the bezout_coeffs function to find the coefficients of a and m
        a_m_coeffs = bezout_coeffs(a, m)
        # Setting up variables to store the coefficients of a and m
        s_coeff_a = a_m_coeffs[a] # Coefficient of a -> s
        t_coeff_m = a_m_coeffs[m] # Coefficient of m -> t

        correct_value = 0 # Variable to store the value of the inverse of 'a' modulo 'm'

        # Setting up conditonal statments to check coefficients are in the range [0, m-1]
        if s_coeff_a >= 0 and s_coeff_a < m:
            correct_value = s_coeff_a 
        elif t_coeff_m >= 0 and t_coeff_m < m:
            correct_value = t_coeff_m
        else:
            raise ValueError("The inverse of 'a' modulo 'm' does not exist")
        
        mod_inv_value = correct_value

    return mod_inv_value # Returning the value of x as the inverse of 'a' modulo 'm'

1. 误解贝祖系数的作用：根据贝祖定理，s*a + t*m = 1（因a和m互质），两边模m可得s*a ≡ 1 mod m——只有s是a的模逆元，t和a的逆元没有任何关系，你错误地将t作为备选逆元。
2. 未正确处理系数范围：当s为负数或大于等于m时，直接判定逆元不存在是错误的。只需对s取模m，就能得到[0, m-1]范围内的最小正逆元，不管s原本是正还是负。

def modinv(a, m):
    GCD_Calculation = gcd(a, m)

    if GCD_Calculation != 1:
        raise ValueError("The given values are not relatively prime")
    elif m < 1:
        raise ValueError("'m' has to be a positive integer")
    else:
        a_m_coeffs = bezout_coeffs(a, m)
        s_coeff_a = a_m_coeffs[a]
        # 对s取模m，直接得到最小正逆元
        mod_inv_value = s_coeff_a % m

    return mod_inv_value

• 输入modinv(3,7)：若贝祖系数返回s=-2，-2 %7=5，而3*5=15≡1 mod7，结果正确。
• 输入modinv(7,19)：若贝祖系数返回s=11，11%19=11，7*11=77≡1 mod19，结果正确；即使返回s=-5，-5%19=14？不对，这里实际贝祖系数应为s=11（11*7 + (-4)*19=1），取模后结果依然正确。

内容的提问来源于stack exchange，提问作者SSingh