中国剩余定理

在去年曾经tutor过一些数学竞赛，很多题目有关一个数除x余y， 然后求这个数是多少的。

比如 一个数当除以3余2，除以5余3，除以7余2，那么这个数是多少

x = 2 mod 3

x = 3 mod 5

x = 2 mod 7

这个时候分成3个mod 部分分别求基础解。

比如第一部分 另外两个mod的乘积为 5 x 7 = 35

然后在mod 3 中求 35 的倒数

35 x 2 = 1 mod 3

再把 倒数 x 一开始余的数 x 另外两个mod 的乘积 = 2 x 2 x 35 = 140

然后同理，求出另外两个mod的结果再加在一起 = 233，

那么所有233 + (3x5x7) x k 的数都满足这个条件

接下来我想尝试写一个python 程序解决所有诸如此类的问题

def inverseMod(number, mod):
    total = 1
    for i in range(mod):
        if (total%number) == 0: 
            return total/number
        total = total + mod
    return False

def chineseRemainingTheory(remainList, modList):
    inverserModList = []
    allProduct = 1
    for i in modList:
        allProduct = allProduct * i
    result = 0
    for index in range(len(remainList)):
        products = (allProduct/modList[index])
        inverse = inverseMod(products%modList[index], modList[index])
        result = result + (inverse * products * remainList[index])
    return result

def main():
	remainList = [2,3,2]
	modList = [3,5,7]
	result = chineseRemainingTheory(remainList, modList)
	print (result, "should = 233")