中国同余定理

历史渊源：物不知数

中国同余定理，又称中国剩余定理（Chinese Remainder Theorem, 简称CRT），是中国古代数学辉煌成就的重要代表之一。其最早记载于南北朝时期（公元4-5世纪）的数学著作《孙子算经》卷下第二十六题，题为“物不知数”。

原文记载：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？” 这一问题的本质是求解一个一次同余方程组。解答者不仅给出了答案“二十三”，还给出了通用的解法口诀：“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。”

数学原理：大衍求一术

要深入理解中国同余定理，必须掌握其严格的数学表述和构造性证明。设 是两两互质的正整数，对于任意整数 ，同余方程组：

在模 的意义下，该方程组有唯一解。解的构造公式为：

其中：

• （总积除以当前模数）
• 是 关于模 的模逆元，即满足 的整数。

示例计算：孙子算经原题

问题：, , 。

1. 计算总积 M：。
2. 计算 Mi：
3. 计算逆元 yi：
   • (因为 ? No. . . Correct.)
   • (Wait, . So . . Correct.)
4. 计算解 x：
5. 取模 M：。

最终解为 23。这与秦九韶口诀“三人同行七十稀”（? No, the口诀 uses 70, 21, 15. Let's check: , , . Yes. My calculated inverses were 2, 1, 1. The口诀 uses 70, 21, 15. . So the口诀 effectively absorbs the multiplier or uses a different set of bases. Actually, the口诀 is: . . Perfect match.

算法实现与代码示例

在现代计算机科学中，中国同余定理不仅是数论的考点，更是算法竞赛和密码学实现的基石。下面提供Python和C++两种语言的实现示例。

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = extended_gcd(b % a, a)
        return g, x - (b // a)  y, y
def modinv(a, m):
    g, x, y = extended_gcd(a, m)
    if g != 1:
        raise Exception('Modular inverse does not exist')
    else:
        return (x % m + m) % m
def chinese_remainder_theorem(pairs):
    """
    pairs: list of tuples (remainder, modulus)
    Example: [(2, 3), (3, 5), (2, 7)]
    """
    # 1. Calculate product of all moduli
    mod_product = 1
    for _, m in pairs:
        mod_product = m
    result = 0
    for a, m in pairs:
        Mi = mod_product // m
        yi = modinv(Mi, m)
        result += a  Mi  yi
    return result % mod_product
Test
print(chinese_remainder_theorem([(2, 3), (3, 5), (2, 7)])) # Output: 23

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= a / b  x;
    return d;
}
ll crt(vector<ll>& a, vector<ll>& m) {
    ll M = 1, ans = 0;
    for (ll x : m) M = x;
    for (int i = 0; i < a.size(); i++) {
        ll Mi = M / m[i];
        ll x, y;
        exgcd(Mi, m[i], x, y);
        ans = (ans + a[i]  Mi  x) % M;
    }
    return (ans % M + M) % M;
}
int main() {
    vector<ll> a = {2, 3, 2};
    vector<ll> m = {3, 5, 7};
    cout << crt(a, m) << endl; // Output: 23
    return 0;
}

public class CRT {
    public static long extendedGCD(long a, long b, long[] xy) {
        if (b == 0) {
            xy[0] = 1;
            xy[1] = 0;
            return a;
        }
        long[] nextXY = new long[2];
        long d = extendedGCD(b, a % b, nextXY);
        xy[0] = nextXY[1];
        xy[1] = nextXY[0] - (a / b)  nextXY[1];
        return d;
    }
    public static long modInverse(long a, long m) {
        long[] xy = new long[2];
        extendedGCD(a, m, xy);
        return (xy[0] % m + m) % m;
    }
    public static long chineseRemainder(long[] a, long[] m) {
        long M = 1;
        for (long val : m) M = val;
        long result = 0;
        for (int i = 0; i < a.length; i++) {
            long Mi = M / m[i];
            long yi = modInverse(Mi, m[i]);
            result = (result + a[i]  Mi % M  yi % M) % M;
        }
        return result;
    }
    public static void main(String[] args) {
        long[] a = {2, 3, 2};
        long[] m = {3, 5, 7};
        System.out.println(chineseRemainder(a, m)); // Output: 23
    }
}

现代应用：从密码学到分布式计算

中国同余定理不仅在古代数学中占据重要地位，在现代科技领域更是不可或缺。以下是其几个核心的应用场景。

网友们还关心：CRT与扩展CRT的区别

标准的中国同余定理要求模数两两互质。然而，在实际问题中，模数往往不互质。这时需要使用扩展中国剩余定理（Extended CRT）。

扩展CRT的处理思路是将两个方程 和 合并为一个方程。通过扩展欧几里得算法，判断方程组是否有解（即 是否整除 ），如果有解，则合并为一个新的模线性同余方程，模数变为 。重复此过程直到所有方程合并完毕。

考研与竞赛复习指南

对于准备考研数学、离散数学或算法竞赛的同学来说，中国同余定理是一个高频考点。以下是复习重点和易错点分析。

易错点提示

• 余数范围：余数必须是非负整数且小于模数。在计算过程中如果出现负数，务必转换为正余数。
• 互质条件：在使用标准CRT公式前，务必检查模数是否两两互质。如果不互质，必须使用扩展CRT。
• 数据溢出：在编程实现时，中间乘积可能远超数据类型范围，需要使用快速乘或大数库，或在每一步进行取模操作。

常见问题解答 (FAQ)

网友们还关心：周边知识拓展

除了中国同余定理本身，许多网友和学子还会关注与之紧密相关的数学概念和技术。以下是对这些周边知识的简要介绍。