中国剩余定理（孙子定理）：数论中的一个关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解方法。

中国剩余定理

适用问题

有以下一元线性同余方程组：

$(S) : {\begin{matrix} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \\ ⋮ \\ x \equiv a_{n} (\mod m_{n}) \end{matrix}$

整数 $m_{1}, m_{2}, \dots, m_{n}$ 其中任两数互质，求解 $x$ .

求解步骤

通解可以用如下方式构造得到：

设 $M = m_{1} \times m_{2} \times \dots \times m_{n} = \prod_{i = 1}^{n} m_{i}$ 是整数 $m_{1}, m_{2}, \dots, m_{n}$ 的乘积，并设 $M_{i} = M / m_{i}, \forall i \in {1, 2, \dots, n}$ ，即 $M_{i}$ 是除了 $m_{i}$ 以外的 $n - 1$ 个整数的乘积。
设 $t_{i} = M_{i}^{- 1}$ 为 $M_{i}$ 模 $m_{i}$ 的数论倒数： $t_{i} M_{i} \equiv 1 (\mod m_{i}), \forall i \in {1, 2, \dots, n} .$
方程组 $(S)$ 的通解形式为： $x = a_{1} t_{1} M_{1} + a_{2} t_{2} M_{2} + \dots + a_{n} t_{n} M_{n} + k M = k M + \sum_{i = 1}^{n} a_{i} t_{i} M_{i}, k \in Z .$ 在模 $M$ 的意义下，方程组 $(S)$ 只有一个解： $x = \sum_{i = 1}^{n} a_{i} t_{i} M_{i} .$

来源：Wikipedia (使用 CC BY-SA 3.0 协议)

其中，求数论倒数（即乘法逆元）的方式是扩展欧几里得算法，不可使用费马小定理。

简单证明

$\begin{aligned} x & = a_{1} t_{1} M_{1} + a_{2} t_{2} M_{2} + \dots + a_{n} t_{n} M_{n} + k M \\ = k M + \sum_{i = 1}^{n} a_{i} t_{i} M_{i}, k \in Z . \end{aligned}$

我们验证该解是否满足原一元线性同余方程组，首先考虑方程组中第一个方程：

$x mod m_{1} = (a_{1} t_{1} M_{1}) mod m_{1} + (a_{2} t_{2} M_{2}) mod m_{1} + \dots + (a_{n} t_{n} M_{n}) mod m_{1} + (k M) mod m_{1}$

首先，由于 $t_{1} M_{1} \equiv 1 (\mod m_{1})$ ，因此 $(a_{1} t_{1} M_{1}) mod m_{1} = a_{1} mod m_{1}$ . 另外由于 $M_{i}, i \in {2, 3, \dots, n}$ 中均包含 $m_{1}$ 因子，因此 $(a_{i} t_{i} M_{i}) mod m_{1} = 0, i \in {2, 3, \dots, n}$ . 综上 $x mod m_{1} = a_{1} mod m_{1}$ ，即 $x \equiv a_{1} (\mod m_{1})$ .

同理可得，该解满足方程组中的所有方程，因此它是方程组的一个解。

扩展中国剩余定理

我们注意到，中国剩余定理的使用条件是整数 $m_{1}, m_{2}, \dots, m_{n}$ 其中任两数互质。如果不满足该条件，中国剩余定理失效。

针对这种情况，我们使用扩展中国剩余定理求解。（该情况有可能无解）

适用问题

有以下一元线性同余方程组：

$(S) : {\begin{matrix} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \\ ⋮ \\ x \equiv a_{n} (\mod m_{n}) \end{matrix}$

不保证整数 $m_{1}, m_{2}, \dots, m_{n}$ 其中任两数互质，问：方程组是否有解？若有解，试求 $x$ .

推导和求解步骤

联立其中两个方程

首先考虑 $(S)$ 中前两个方程：

$\begin{matrix} (1) & {\begin{matrix} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \end{matrix} \end{matrix}$

$(1)$ 经过变形可得到：

$\begin{matrix} (2) & {\begin{matrix} x = a_{1} + m_{1} k_{1} \\ x = a_{2} + m_{2} k_{2} \end{matrix} \end{matrix}$

求解联立方程组

消去 $(2)$ 中 $x$ 并进行变形，得：

$\begin{matrix} (3) & m_{1} k_{1} - m_{2} k_{2} = a_{2} - a_{1} \end{matrix}$

该式对应的裴蜀等式为 $(4)$ ，其中 $d = gcd (m_{1}, m_{2})$ ：

$\begin{matrix} (4) & m_{1} k_{1}^{'} - m_{2} k_{2}^{'} = d \end{matrix}$

通过扩展欧几里得算法，求得 $k_{1}^{'}, k_{2}^{'}, d$ ，若 $a_{2} - a_{1}$ 是 $d$ 的倍数，即原式有解，一个特解为：

${\begin{matrix} k_{1}^{*} = k_{1}^{'} \cdot (a_{2} - a_{1}) / d \\ k_{2}^{*} = k_{2}^{'} \cdot (a_{2} - a_{1}) / d \end{matrix}$

若 $a_{2} - a_{1}$ 不是 $d$ 的倍数，那么原一元线性同余方程组无解，可停止下面的计算。得到特解后，我们可以构造出通解（构造方式见扩展欧几里得算法的笔记）：

${\begin{matrix} k_{1} = k_{1}^{*} + t \cdot (m_{2} / d) \\ k_{2} = k_{2}^{*} - t \cdot (m_{1} / d) \end{matrix}, t \in Z$

将解回代

将解出的 $k_{1}$ 回代到 $(2)$ 中第一个方程，得到：

$\begin{matrix} (5) & \begin{aligned} x & = a_{1} + m_{1} k_{1} \\ = a_{1} + m_{1} \cdot [k_{1}^{*} + t \cdot (m_{2} / d)] \\ = (a_{1} + m_{1} k_{1}^{*}) + (m_{1} m_{2} / d) \cdot t \\ = (a_{1} + m_{1} k_{1}^{*}) + lcm (m_{1}, m_{2}) \cdot t \end{aligned} \end{matrix}$

我们可以发现， $(5)$ 式与 $(2)$ 式的结构非常相似，结构均为：

$\begin{matrix} (6) & x = C_{1} + C_{2} \cdot m (C_{1}, C_{2} 为常数, m 为自变量) \end{matrix}$

将方程组合并为一个方程

我们上面的过程，即可看作将 $(2)$ 的两个式子合并为了 $(6)$ 这样的一个式子， $(6)$ 和 $(2)$ 同解。那么我们可以不断重复这个步骤，将式子不断合并。即再将 $(6)$ 与 $(S)$ 中第三个式子合并得到新式子，再将新式子与 $(S)$ 中第四个式子合并……

合并最后的结果便是一个式子，我们假设这个式子为：

$\begin{matrix} (7) & x = α + b \cdot β \end{matrix}$

$(7)$ 式非常简单就能解出结果，而且原方程组 $(S)$ 与 $(7)$ 同解，那么我们解 $(7)$ 这个方程即可得到 $(S)$ 的解。

求解最终合并式

若我们要求得最小的正整数解， $(7)$ 式的解其实就是 $α mod β$

模板

typedef long long ll;

ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if (!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// 如果中途输出-1,-1则需要立即停止
// first-a second-mod
pair<ll, ll> excrt(pair<ll, ll> a, pair<ll, ll> b)
{
    ll ya, yb;
    ll d = exgcd(a.second, b.second, ya, yb);
    if ((b.first - a.first) % d)
        return {-1, -1};
    ya *= (b.first - a.first) / d;
    ll tmp = b.second / d;
    ya = (ya % tmp + tmp) % tmp;
    a.first += a.second * ya;
    a.second = a.second / d * b.second;
    return a;
}

典型例题

原题链接：https://www.acwing.com/problem/content/206/

注意：

为防止乘法溢出，建议先除后乘。
C 语言负数取模会成负数，因此取模需要写成 ( $α mod β + β) mod β$ 这种形式。
程序实现时并没有使用上述过程中的那么多变量，同一个变量被重复利用。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int MAXN = 30;
int n;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int main()
{
    cin >> n;
    LL a1, m1;
    cin >> a1 >> m1;
    for (int i = 2; i <= n; i++)
    {
        LL a2, m2, y1, y2;
        cin >> a2 >> m2;
        LL d = exgcd(a1, a2, y1, y2);
        if ((m2 - m1) % d)
        {
            cout << -1 << endl;
            return 0;
        }
        y1 *= (m2 - m1) / d;
        LL tmp = a2 / d;
        y1 = (y1 % tmp + tmp) % tmp;
        m1 += a1 * y1;
        a1 = abs(a1 / d * a2);
    }
    cout << (m1 % a1 + a1) % a1 << endl;
    return 0;
}

数论 | 中国剩余定理及其扩展

中国剩余定理

适用问题

求解步骤

简单证明

扩展中国剩余定理

适用问题

推导和求解步骤

模板

典型例题

添加新评论

最新文章

分类

标签

其它