中国剩余定理

知识回顾-线性同余方程相关定理

• 定理1：线性同余方程： \[ax \equiv k \pmod{b} \ (\text{即：} ax + by = k)\] 对于未知量\(x\)有解，当且仅当\(\gcd(a, b) \mid k\)。
• 如何证明？
  • 充分性证明…（贝祖定理）
  • 必要性证明…（提取公因数\(\gcd(a, b)\)）

通过前面的学习，我们知道：

求一个最小的正整数\(x\)，要求它满足\(ax \equiv k \pmod{b}\)就是典型的线性同余方程问题。

新问题来了：

如果希望\(x\)同时满足多个模线性方程呢？比如：

\(\boldsymbol{x \equiv 2 \pmod{3}}\)

\(\boldsymbol{x \equiv 3 \pmod{5}}\)

引子

经典问题——物不知数

“今有物，不知其数，三三数之余二 ，五五数之余三 ，七七数之余二，问物几何？” ——《孙子算经》

以上问题等价于求以下同余方程组的正整数解： \[ x \equiv 2 \pmod{3} \] \[ x \equiv 3 \pmod{5} \] \[ x \equiv 2 \pmod{7} \]

中国剩余定理-特殊

中国剩余定理

定理：若 \(m_1, m_2, \dots m_n\) 是两两互质的正整数，则对于任意的 \(n\) 个整数 \(a_1, a_2 \dots a_n\)，同余方程组 \(x \equiv a_i \pmod{m_i}\) \(i = 1, 2 \dots n\) 有整数解，并且在模 \(M\) 下解唯一。

构造方程组的解为：\(x = a_1 M_1 x_1 + a_2 M_2 x_2 + \dots + a_n M_n x_n\)

其中：\(M = \prod m_i\) ，\(M_i = M / m_i\)，\(x_i\) 是线性同余方程 \(M_i x_i \equiv 1 \pmod{m_i}\) 的一个解（因为 \(M_i\) 和 \(m_i\) 互质，必有解）。

问题已经转化为求解n个线性同余方程的解

代码

扩展欧几里得算法

int ex_gcd(int a,int b, int &x, int &y){
    if (b == 0){ x = 1, y = 0;   return a;   }
    int d = ex_gcd(b, a%b, x, y);
    int tmp = x;
    x = y;                            // 原理：见上页证明
    y = tmp - (a/b)*y;                // 原理：见上页证明
    return d;
}

中国剩余定理-参考代码

int ChineseRemain(int n)
{
    int i, Mi, xi, yi, d, Ans=0;
    M = 1;
    for(i=1; i<=n; i++) M *= m[i];
    for(i=1; i<=n; i++){
        Mi = M / m[i];
        d = ex_gcd(Mi, m[i], xi, yi);
        Ans = (Ans + Mi * xi * a[i]) % M;
    }
    return (Ans + M) % M;
}

前提：模数全部互质

算经例题解答：

实例分析——物不知数

三三数余二 ，五五数余三 ，七七数余二，问物几何？

求解过程：

\(m[1] = 3\)； \(m[2] = 5\)； \(m[3] = 7\)；

\(a[1] = 2\)； \(a[2] = 3\)； \(a[3] = 2\)；

\(M=3*5*7=105\)； \(M1=5*7=35\) \(M2=3*7=21\) \(M3=3*5=15\)

\(x1=2\) \(x2=1\) \(x3=1\)

\(x = (2*35*2+3*21*1+2*15*1)\%105 = 233\%105 = 23\)

问题的通解是：\(23 + 105 * k\)

中国剩余定理-一般

引子

先说点别的：

• 设想一下求N个正整数的LCM的问题：

• 假设已经求得前i个数的LCM是K，下一步求前i+1个数的LCM的时候是否可以这样——

• 判断K是否为第i+1个数的倍数，如果是，得解；

• 如果不是，在K的基础上不断增加K，直到这个数是第i+1个数的倍数！

求解思路

中国剩余定理的一般情况：

• 数学归纳法——
• 假设已经求出前k-1个方程构成的方程组的一个解x。 记\(m=\text{lcm}(m_1, m_2, \dots m_{k-1})\)，则x+i*m是前k-1个方程的通解。
• 考虑第k个方程，求出一个整数t，使得\(x + t * m \equiv a_k \pmod{m_k}\)， 该方程等价于\(m * t \equiv a_k - x \pmod{m_k}\)，其中t是未知量。
• 可以判断是否有解，若有解，则可以用扩欧求出这个解。也就是说，\(x' = x + t * m\) 就是前k个方程构成的方程组的一个解。

参考代码：

扩展中国剩余定理-参考代码

int Ex_Crt()
{ int aa = b[1],rr=a[1],x,y;
  for(int i=2;i<=n;++i)
  { int bb = b[i];
    int c = a[i]-rr;    int d = Ex_gcd(aa,bb,x,y);
    if(c%d)      return -1;      //如果c不能整除d，不存在整数解
    c = c/d;     bb = bb/d;
    x = (x*c%bb+bb)%bb;
    int lcm = aa*bb;
    rr = (x*aa%lcm+rr)%lcm;     aa = lcm ;
  }
  return rr==0? aa:rr;
}

小结

1、中国剩余问题的本质 （模数互质的模线性方程组）

2、中国剩余问题的求解

3、中国剩余问题的一般情况（模数不保证互质） （扩展中国剩余定理）

模板性质强