编程实现计算同余式ax≡1(mod m)的解

这里提供一个Python实现：

def extended_euclidean_algorithm(a, b):
    """
    扩展欧几里得算法求解ax + by = gcd(a, b)中的x和y
    """
    if b == 0:
        return 1, 0, a
    else:
        x, y, gcd = extended_euclidean_algorithm(b, a % b)
        return y, x - (a // b) * y, gcd

def solve_congruence(a, m):
    """
    解同余式ax ≡ 1 (mod m)中的x
    """
    x, _, gcd = extended_euclidean_algorithm(a, m)
    if gcd != 1:
        # 如果a和m不互质，则无解
        return None
    else:
        return (x % m + m) % m  # 返回正整数解

使用示例：

>>> solve_congruence(3, 7)
5
>>> solve_congruence(4, 8)
None
>>> solve_congruence(5, 9)
2