中国剩余定理（Chinese Remainder Theorem，CRT）又称孙子定理，是数论中的一个定理。
古典数学问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
白话文就是：某物的数量除以3余2，除以5余3，除以7余2，某物的数量是多少？
以下算法有错误
#!/usr/bin/env python
from functools import reduce
def egcd(a, b):
"""扩展欧几里得"""
if 0 == b:
return 1, 0, a
x, y, q = egcd(b, a % b)
x, y = y, (x - a // b * y)
return x, y, q
def chinese_remainder(pairs):
"""中国剩余定理"""
mod_list, remainder_list = [p[0] for p in pairs], [p[1] for p in pairs]
mod_product = reduce(lambda x, y: x * y, mod_list)
mi_list = [mod_product//x for x in mod_list]
mi_inverse = [egcd(mi_list[i], mod_list[i])[0] for i in range(len(mi_list))]
x = 0
for i in range(len(remainder_list)):
x += mi_list[i] * mi_inverse[i] * remainder_list[i]
x %= mod_product
return x
if __name__=='__main__':
print(chinese_remainder([(3, 2), (5, 3), (7, 2)]))
