中国剩余定理和求乘法的逆元
文/王彦会
普及个知识:中国剩余定理在小学课本中有，大学也讲，所以老少皆宜。古代中国研究已很精辟，并广泛应用。历代皇帝重视历法，历法中大量用到这种计算，古代中国历法精确就得益于此。农历是阴阳合历，既照顾太阳又照顾月亮，较复杂，我不懂历法，不知具体如何算。在现代科技中也会用到，如公钥密码体制中的公钥和私钥的计算。
法:若某数除以ABC余分别为r1，r2，r3，求此数？
求除A余r1要在BC的倍数中求，先求乘以BC使余数(/A)为1的乘率m，(或直接得出余r1的乘率)，则m乘r1与BC的积满足/A余r1。
依次类推得到分别满足BC的解，再加起来就得到答案，除以最小公倍数得到的余数就是最小的解，最小解是唯一的。
当数据很大不便于从1试到m，求m的方法古人叫“大衍求一术”，其实就是现代的求模的逆元，若ed/P余1则e与d互为逆元。查书，用到辗转相除法，好象没有公式，只讲到方法:辗转相除(用余数再去除除数)到余1再逆推回去。
公式比较复杂，最后结果需要分3种情况输出，不方便不推导了。
下面图片是陆元鸿教授给出的矩阵解法：（教授给出的例子分别是一类，我补充了一个就是7/4的逆元为3的例子，是又一类，加上这个就完整了。）
图片附于后面。（这种方法求逆元，我已经编程，有需要的请与我联系）
下面举个例子，就是用此方法来求逆元进而解决中国剩余定理的问题：
题：
今有物不知其数，三、三数之余2，五、五数之余1，七、七数之余4，13、13数之余10，55、55数之余21，56、56数之余39，问物几何？
解：
21/5余数1，
39/7余数4，
与前面不矛盾，所以，有解，
3*5*7*13*11*8=120120，（这就是最小公倍数）
120120/3=40040，
120120/5=24024，
120120/7=17160，
120120/13=9240，
120120/55=2184，
120120/56=2145，
40040模3 的逆元为：2，则满足3，3数余2的为：2*40040*2=160160，
24024模5 的逆元为：4，则满足5，5数余1的为：4*24024*1=96096，
17160模7 的逆元为：5，则满足7，7数余4的为：5*17160*4=343200，
9240模13 的逆元为：4，则满足13，13数余10的为：4*9240*10=369600，
2184模55 的逆元为：24，则满足55，55数余21的为：24*2184*10=524160，（因为96096/55=1747余11，加10就会余数为21），
2145模56 的逆元为：33，则满足56，56数余39的为：33*2145*7=495495，（因为343200/56=6128余32，加7就会余数为39），
495495/56=8848余7，所以，正确，
160160+96096+343200+369600+524160+495495=1988711，
1988711/3=662903余2，
1988711/5=397742余1，
1988711/7=284101余4，
1988711/13=152977余10，
1988711/55=36158余21，
1988711/56=35512余39，所以，都符合实际，正确！
1988711/120120=16余66791，所以，最小解为66791.（这类问题有无穷解，最小的一个是唯一的）
求40040模3 的逆元的手工计算：（我是用程序算出来的，其实就是古人说的求余数为1的乘率）
40040/3的余数为2，2*2/3余数为1，所以，逆元为2.
其它依次类推，2184/55=余39，要至少试验23次，得到24*39/55=余数1，
2145/56余数17，至少32次得到33*17/56余数1.
手工计算是费劲，需要技巧，注意具体问题与普遍公式的区别，特殊的差异，题目多拐个弯就容易出错，注意！
比如：96096/55=1747余11，不是余数为0，后面的一项必须要加上11才能为21，且加数必须为5的倍数（或其他的前面的模，一般都对不必太在意）。
另一位网友的解法：
记住一条即可，任意数做被乘数，从0递增到P-1倍，加任意一个数，在这p个数中一定有一个数被P整除。等差数列如下：m+（i-1）T，1≤i≤P,则此数列中一定有一个值被P整除。m为事先给的值，T为周期值（或者跨度数，步长），P为给定的值，且与m互质（这个方法就是穷举法，递推法，数据小的时候行，看上去还简单，数据大的时候就无法用，还是前面的方法具有普遍性）。
这种方法很有用，实际生活中工作中总会遇到此类问题，比如解一次不定方程的时候就用到，和求中国剩余定理的问题一样。应该普及，欢迎指导，欢迎探讨！
换一换
