数论入门:四大定理之孙子剩余定理

​

内容

孙子定理也叫中国剩余定理，也就是Chinese remainder theorem，简称CRT，是中国古代求解一次线性同余方程组的方法，最早源于南北朝时期的数学著作《孙子算经》中的一到叫“物不知数”的问题，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

物不知数中给出了这样的一个问题：

$(s):$

$x≡a_1(\mod m_1)$

$x≡a_2(\mod m_2)$

.

.

.

$x≡a_n(\mod m_n)$

中国剩余定理给出了这个方程有解的条件，以及使用构造法给出了方程的解：

假设$m_1,m_2,…,m_n$两两互质，则对任意的整数：$a_1,a_2,…,a_n$，方程组（s）有解，并且通解可以用如下方式构造得到：

设$M=m_1\times m_2\times …\times m_n$，并设$M_i=M/m_i,i\in (1,2,…,n)$，设$t_i=inv(M_i,m_i)$即$M_i$模$m_i$的逆元，则有：$t_i\times M_i≡1(\mod m_i)$

于是（S）的通解为$x=a_1\times t_1\times M_1+a_2\times t_2\times M_2+…+a_n\times t_n\times M_n+K\times M（k \in Z）$

再模M的情况下，x的值唯一，即：$x=(a_1\times t_1\times M_1+a_2\times t_2\times M_2+…+a_n\times t_n\times M_n) \mod M$

证明

直接证明

我们从构造的假设出发来证明这样的解的正确性：

由于$t_i$是$M_i$取模$m_i$下的逆元，则可得到式子：

$t_i\times M_i≡1(\mod m_i)$

于是两边同时乘以$a_i$就得到式子：

$a_i\times t_i\times M_i≡a_i(\mod m_i)$

（能同时乘以$a_i$是因为$a_i$小于$m_i$，所以$a_i$与$m_i$互质）

再通过$m_i$的性质可以得到：

$a_i\times t_i\times M_i≡0(\mod m_j)$其中$j \in (1,2,…,n) 且 j\neq i$

则由以上性质可以得到$x=a_1\times t_1\times M_1+a_2\times t_2\times M_2+…+a_n\times t_n\times M_n$是方程组的一个解。

再者，若$x_1$与$x_2$都为方程组的解，那么将会得到如下等式:

$x_1-x_2≡0(\mod m_i)$

由于$m_1,…,m_n$中的数两两互素，那么两边依次同时乘以这些数等式依然成立，于是得到:

$(x_1-x_2)*M=0(\mod M)$

然后由取模运算的性质得到：

$x_1-x_2=0(\mod M)$

即两个解之间的差为M的倍数，最小为M，于是满足以下式子：

$x=a_1\times t_1\times M_1+a_2\times t_2\times M_2+…+a_n\times t_n\times M_n+K\times M（k \in Z）$

的x都是方程的解。

构造思考过程

这里为了更清晰的描述这个证明，我们举个例子来分析一下思考构造的过程：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

就用孙子算经中提出的问题来举例，根据题面描述，我们能提炼出如下方程:

$(s):$

$x≡2(\mod 3)$

$x≡3(\mod 5)$

$x≡2(\mod 7)$

于是会想如果把这些方程分别求解，那么解的结果会是什么呢？

可以想到由于存在：

$x_1\times inv(x_1,3)≡1(\mod 3)$

$x_2\times inv(x_2,5)≡1(\mod 5)$

$x_3\times inv(x_3,7)≡1(\mod 7)$

于是让等式两边同时乘以对应的余数：

$2\times x_1\times inv(x_1,3)≡2(\mod 3)$

$3\times x_2\times inv(x_2,5)≡3(\mod 5)$

$2\times x_3\times inv(x_3,7)≡2(\mod 7)$

设：

$a=2\times x_1\times inv(x_1,3)$

$b=3\times x_2\times inv(x_2,5)$

$c=2\times x_3\times inv(x_3,7)$

于是思考这些数加起来，即$a+b+c$，能不能构造出结果呢？，显然是不能的，那么是因为什么原因导致不能呢？因为在取模3时虽然a取模3能得到2，但是b，c取模3并不为0。

于是为了解决这个问题，我们令：

$x_1=5\times 7$

$x_2=3\times 7$

$x_3=3\times 5$

就能解决这个问题了，于是s的解就是：

$a+b+c=2\times 5\times 7\times inv(5\times 7,3)+3\times 3\times 7\times inv(x_2=3\times 7,5)+2\times 3\times 5\times inv(3\times 5,7)=233$

那么最小的解就是$233\mod (2\times 5\times 7)=23$。

代码

取模的数互质的情况

1
2
3
4
5
6
7
8
9
10
11

//需使用求逆元的函数（此代码中未给出）
//n个方程：x=a[i](mod m[i]) (0<=i<n)
LL china(int n, LL *a, LL *m){
    LL M = 1, ret = 0;
    for(int i = 0; i < n; i ++) M *= m[i];
    for(int i = 0; i < n; i ++){
        LL w = M / m[i];
        ret = (ret + w * inv(w, m[i]) * a[i]) % M;
    }
    return (ret + M) % M;
}

扩展中国剩余定理

从之前证明的中国剩余定理来看，最小解的构造需要取模数两两互质，那么如果并不能保证两两互质，问最小解，那么要怎么求呢？

下面介绍中国剩余定理的扩展。

证明

对于两组方程的情况：

$x≡b_1(\mod a_1) $

$x≡b_2(\mod a_2) $

通过转化得到以下方程：

$x=a_1\times x_1+b_1 $

$x=a_2\times x_2+b_2 $

于是我们尝试合并两方程，即：

$a_1\times x_1+b_1=a_2\times x_2+b_2 $

移项得：

$a_1\times x_1+（-a_2）\times x_2=b_2-b_1 $

这个式子是不是很眼熟o(￣▽￣)ｄ

没错是斐蜀定理本定理没错了

于是这个方程有解的条件就是当$gcd(a_1,a_2)|(b_2-b_1)$.

既然满足斐蜀定理，那么我们就能通过拓展欧几里得算法求解$x_1$的解了,于是我们先求接方程$a_1\times x_1+（-a_2）\times x_2=gcd(a_1,a_2) $, 假设求得的解为$K_1,K_2$，于是带入原式为：

$a_1\times K_1+（-a_2）\times K_2=gcd(a_1,a_2) $

然后两边同时乘以$(x_2-x_1)/gcd(a_1,a_2)$

于是得到：

$a_1\times K_1\times (x_2-x_1)/gcd(a_1,a_2)+（-a_2）\times K_2\times (x_2-x_1)/gcd(a_1,a_2)=b_2-b_1 $

于是有对应关系得到：

$x_1=K_1\times (x_2-x_1)/gcd(a_1,a_2)$

$x_2=K_2\times (x_2-x_1)/gcd(a_1,a_2)$

于是原方程为：

$x=K_1\times (x_2-x_1)/gcd(a_1,a_2)\times a_1+b_1$

$x=K_2\times (x_2-x_1)/gcd(a_1,a_2)\times a_2+b_2$

由于解$K_1,K_2$不只一组，所以对应的x也不一样，于是考虑两个x之间的差值d，由第一个方程可以知道d是$(x_2-x_1)/gcd(a_1,a_2)\times a_1$的倍数。

而由第二个方程可以知道d也是$(x_2-x_1)/gcd(a_1,a_2)\times a_2$的倍数。

所以d一定是$(a_1\times a_2)/gcd(a_1,a_2)$的倍数

即d是$lcm(a_1,a_2)$的倍数。

于是通过第一个方程构造x，得到：

$x=a_1\times x_1+b_1+t\times lcm(a_1,a_2)$

于是上述方程组可以合并为：

$x≡a_1\times x_1+b_1(\mod lcm(a_1,a_2)) $

于是我们就可以通过上述方法一直合并下去最合并为一个方程然后求接。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

#include<iostream>
#include<algorithm>
#include<math.h>
using namespace std;
typedef long long ll;
ll n,m;
ll a[1000];
ll b[1000];
void exgcd(ll a,ll b,ll &d,ll &x,ll &y)
{
    if(b)
    {
        exgcd(b,a%b,d,x,y);
        ll temp=x;
        x=y;
        y=temp-a/b*y;
    }
    else
    {
        x=1;
        y=0;
        d=a;
    }
}
int main()
{
	std::ios::sync_with_stdio(false);
  ll t;
  cin>>t;
  ll num=1;
  while(t--)
  {
    cin>>m;
    for(ll i=0;i<m;i++)
    {
      cin>>b[i];
    }
    for(ll j=0;j<m;j++)
    {
      cin>>a[j];
    }
    ll F=(a[0]%b[0]+b[0])%b[0];
    bool flat=true;
    for(ll i=0;i<m-1;i++)
    {
      ll k1,k2,d;
      exgcd(b[i],b[i+1],d,k1,k2);
      //cout<<k1<<' ';
      if((a[i+1]-a[i])%d)
      {
        flat=false;
        break;
      }
      k1*=(a[i+1]-a[i])/d;
      F=k1*b[i]+a[i];
      b[i+1]=b[i]/d*b[i+1];
      F=(F%b[i+1]+b[i+1])%b[i+1];
      a[i+1]=F;
      //cout<<F<<' '<<d<<' '<<k2<<endl;
    }
    if(!F)
    F+=b[m-1];
    if(flat)
    cout<<"Case "<<num++<<": "<<F<<endl;
    else
    cout<<"Case "<<num++<<": "<<-1<<endl;
  }
	return 0;
}

参考链接

Ⅰ.中国剩余定理证明

Ⅱ.扩展中国剩余定理证明