中国剩余定理（孙子定理）

中国剩余定理

在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二（除以余），五五数之剩三（除以余），七七数之 剩二（除以余），问物几何？”这个问题称为“孙子问题”，该问题的一般解法国际上称为“中国剩余定理”。

具体解法分三步：

1. 找出三个数：从和的公倍数中找出被除余的最小数，从和的公倍数中找出被除余的最小数，最后从和的公倍数中找出除余的最小数。
2. 用乘以（为最终结果除以的余数），用乘以（为最终结果除以的余数），同理，用乘以（为最终结果除以的余数），然后把三个乘积相加得到和。
3. 用除以三个数的最小公倍数，得到余数，即。这个余数就是符合条件的最小数。

首先，我们假设是满足除以余的一个数，比如等等，也就是满足的一个任意数。同样，我们假设是满足除以余的一个数，是满足除以余的一个数。

有了前面的假设，我们先从这个角度出发，已知满足除以余，能不能使得的和仍然满足除以余？进而使得的和仍然满足除以余？

这就牵涉到一个最基本数学定理，如果有,则有(为非零整数)，换句话说，如果一个除法运算的余数为，那么被除数与倍的除数相加（或相减）的和（差）再与除数相除，余数不变。这个是很好证明的。

以此定理为依据，如果是的倍数，就依然满足除以余。同理，如果也是的倍数，那么的和就满足除以余。这是从的角度考虑的，再从的角度出发，我们可推导出以下三点：

• 为使的和满足除以余，和必须是的倍数。
• 为使的和满足除以余，和必须是的倍数。
• 为使的和满足除以余，和必须是的倍数。

因此，为使的和作为“孙子问题”的一个最终解，需满足：

1. 除以余，且是和的公倍数。
2. 除以余，且是和的公倍数。
3. 除以余，且是和的公倍数。

所以，孙子问题解法的本质是从和的公倍数中找一个除以余的数，从和的公倍数中找一个除以余的数，从和的公倍数中找一个除以余的数，再将三个数相加得到解。在求时又用了一个小技巧，以为例，并非从和的公倍数中直接找一个除以余的数，而是先找一个除以余的数，再乘以。也就是先求出和的公倍数模下的逆元，再用逆元去乘余数。

最后，我们还要清楚一点，只是问题的一个解，并不是最小的解。如何得到最小解？我们只需要从中最大限度的减掉掉的公倍数即可。道理就是前面讲过的定理“如果，则有。所以就是最终的最小解。

这样就得到了中国剩余定理的公式：

设正整数两两互素，则同余方程组

那么再看提到的一元线性同余方程：(先做几个设定：设为能够被整除，但是除以正好余1)

就是我们要求的一个解，解集为。

剩下的问题就变成了如何求解$ N_{1}, N_{2} … N_{n}$，我们继续向下看：

假设 为任意整数。

因为的性质，可以表示为：

推到现在有没有感觉很熟悉，对的！这个就是扩展欧几里德：

对于, 存在;

存在,

对于

套用一下扩展欧几里德求出 就可以求解出。有了求出就是分分钟的事情！

Code：

//中国剩余定理模板
ll china(int a[],int b[],int n)//a[]为除数，b[]为余数
{
    int M=1,y,x=0;
    for(int i=0; i<n; ++i) //算出它们累乘的结果
        M*=a[i];
    for(int i=0; i<n; ++i)
    {
        int w=M/a[i];
        int tx=0;
        int t=exgcd(w,a[i],tx,y);//计算逆元
        x=(x+w*(b[i]/t)*x)%M;
    }
    return (x+M)%M;
}