中国剩余定理又称孙子定理,是数论中一个重要定理。最早可见于我国的数学著作《孙子算经》卷下“物不知数”问题,原文如下:
有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?即,一个整数除以三余二,除以五余三,除以七余二,求这个整数。
把这题转化成现代数学问题:
求一个数x,该数除以3余2,除以5余3,除以7余2
把以上问题转化为一般方程的形式
根据中国剩余定理解如下
其中
python代码实现
n = int(input())
b = list(map(int, input().split())) # 余数
m = list(map(int, input().split())) # 模数
M = [0] * n
m_total = 1
x = 0 # 解,初始化为0
for i in range(n):
m_total *= m[i] # 计算m_total
for i in range(n):
M[i] = m_total // m[i] # 计算M[i]
for i in range(n):
x += b[i] * M[i] * pow(M[i], -1, m[i]) # pow(M[i], -1, m[i])表示M[i]模m[i]的逆元
print(x % m_total) # 该解有无数个,取一个模m_total的最小正整数解
第一行输入有几个方程
第二行输入每个方程的余数
第三行输入每个方程的模数
如一开始《孙子算经》的那题输入
3
2 3 2
3 5 7
结果为