编程实现计算中国剩余定理

下面是Python实现中国剩余定理的代码：

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def chinese_remainder_theorem(n, a):
    sum = 0
    prod = 1
    for i in n:
        prod *= i

    for i in range(len(n)):
        m = prod // n[i]
        gcd, inv, y = egcd(n[i], m)
        sum += a[i] * inv * m

    return sum % prod

n = [3, 5, 7]
a = [2, 3, 2]
print(chinese_remainder_theorem(n, a)) # 输出22

上述代码中，`egcd`函数用于求解扩展欧几里得算法的解，`chinese_remainder_theorem`函数则是实现了中国剩余定理的具体计算过程。在主函数中，给定了三个模数和对应的余数，计算出了最小的正整数$x$，使得$x\equiv2\pmod{3}$，$x\equiv3\pmod{5}$，$x\equiv2\pmod{7}$，并输出了$x$的值，即22。