中国剩余定理（CRT）孙子定理学习笔记

在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。 用到数学公式： ① 如果a%b=c，那么如果x%b=c/2，此时x=a/2； 也就是说除数相等时，被除数和余数是成比例的。 ② 如果a%b=c，那么 (a + k*b)%b=c，其中k为整数 具体解法：
在3和5的公倍数中找出除以7余1的最小数（15） 在3和7的公倍数中找出除以5余1的最小数（21） 在5和7的公倍数中找出除以3余1的最小数（70）
总结：假设整数m1,m2,…,mn两两互质; M=m1×m2×⋯×mn，即M是整数m1,m2,…,mn的乘积; 并设Mi=M/mi,∀i∈{1,2,3,…,n}是除了mi以外的n−1个整数的乘积; 设ti是Mi模mi下的逆元。 此步即求ti。
用

中国剩余定理（CRT）孙子定理学习笔记最先出现在Python成神之路。