中国剩余定理公式推导（大衍归一术）@外焦兔

解孙子定理（求同余方程组）经典算法即大衍归一术，除数各不相同，利用逆元乘余数避开同余的除法运算，但局限于方程组中各除数应保持互质。

alt

运用衍数m/mi

alt

以三个经典同余方程组为例，“三三数之剩二（除以3余2），五五数之剩三（除以5余3），七七数之剩二（除以7余2）”先求出5和7的 公倍数 模3下的逆元，再用逆元去乘余数。

由衍数实现公倍数，公倍数乘以对应的逆元得到符合条件的模后为1的数，再乘余数实现符合条件（公倍数）的模后为余数的数，即大衍归一术。

alt

因此式子成立 alt 因此式2也成立：（m1整除m）在同余公式中，如果 alt

如果a恒等于b(mod m)即m整除于a-b,那么如果m1整除于a-b,m1同样与a,b同余，即上式成立。同理，X恒等于（...）mod(可整除m的数例如m1,m2,m3...均可以将题目逆推出来)

也就是从反方向上印证了只有m是m1,m2,m3...连乘（其公倍数）才可以将其所有同余方程全部逆推出来。

也印证了经典题目中（%105）的正确性和唯一性。 alt 由此可以导出： alt

能够反向将问题推出来。