中国剩余定理解题实例

本篇文章针对中国剩余定理，给出纸笔计算过程，并引申出python代码实现

现给出题目

解同余方程组：

x≡2 mod 5
x≡3 mod  11
x≡5 mod  17

1.纸笔计算

当计算量更大时，可以使用python实现：

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

def mod_inv(a, m):
    g, x, y = egcd(a, m)
    return x % m  # 确保返回正整数

def crt(remainders, moduli):
    M = 1
    for m in moduli:
        M *= m
        
    solution = 0
    for i in range(len(remainders)):
        ai = remainders[i]
        mi = moduli[i]
        Mi = M // mi
        inv = mod_inv(Mi, mi)
        solution = (solution + ai * Mi * inv) % M
        
    return solution

在使用时，需要给出remainders和moduli两个数组，例如：

#   x ≡ 2 (mod 5)
#   x ≡ 3 (mod 11)
#   x ≡ 5 (mod 17)
remainders = [2, 3, 5]
moduli = [5,11,17]