中国剩余定理解题大全

⚡ 定理概述：什么是中国剩余定理？

中国剩余定理（Chinese Remainder Theorem，简称CRT），又名孙子定理，是数论中一个极为重要的定理。它主要解决的是同余方程组的求解问题。简单来说，如果已知一个整数 x 被两两互质的整数 m1, m2, ..., mn 除，得到的余数分别为 a1, a2, ..., an，那么 x 在模 M = m1 m2 ... mn 的意义下，存在唯一解。

这一定理不仅在纯数学领域具有核心地位，在计算机科学、密码学、信号处理等领域也有广泛的应用。对于数学爱好者、计算机专业学生以及参加算法竞赛的选手来说，掌握中国剩余定理解题大全中的技巧是必备技能。

📜 历史渊源：从《孙子算经》到现代数学

中国剩余定理的历史可以追溯到中国古代。最早的记载见于公元5世纪左右的《孙子算经》。其中著名的“物不知数”问题奠定了该定理的基础。

🧮 数学原理：严谨的推导过程

理解中国剩余定理的关键在于模逆元的存在性。由于 m1, m2, ..., mn 两两互质，对于任意 i，Mi = M/mi 与 mi 互质。根据数论基本定理，存在整数 yi 使得 Mi yi ≡ 1 (mod mi)。

构造解的方法

我们构造如下解：
x = a1 M1 y1 + a2 M2 y2 + ... + an Mn yn

验证：x 模 mi 时，除了第 i 项 ai Mi yi 等于 ai 1 1 = ai 外，其他所有项都包含 mi 作为因子，因此模 mi 余 0。故 x ≡ ai (mod mi) 对所有 i 成立。

🛠️ 解题步骤：经典例题解析

下面通过一个经典例题，演示如何使用中国剩余定理进行手动计算。

详细求解过程

1. 计算总模数 M：
   M = 3 5 7 = 105
2. 计算 Mi 和 yi：
   • 对于 m1=3:
     M1 = 105 / 3 = 35
     求解 35 y1 ≡ 1 (mod 3) → 2 y1 ≡ 1 (mod 3) → y1 = 2
   • 对于 m2=5:
     M2 = 105 / 5 = 21
     求解 21 y2 ≡ 1 (mod 5) → 1 y2 ≡ 1 (mod 5) → y2 = 1
   • 对于 m3=7:
     M3 = 105 / 7 = 15
     求解 15 y3 ≡ 1 (mod 7) → 1 y3 ≡ 1 (mod 7) → y3 = 1
3. 计算特解 x：
   x = (2 35 2 + 3 21 1 + 2 15 1) mod 105
x = (140 + 63 + 30) mod 105
x = 233 mod 105
x = 23

验证：
23 ÷ 3 = 7 ... 2 (符合)
23 ÷ 5 = 4 ... 3 (符合)
23 ÷ 7 = 3 ... 2 (符合)
故最小正整数解为 23。

💻 编程实现：多语言代码示例

在算法竞赛和实际开发中，手动计算效率低下。以下是使用 扩展欧几里得算法 实现 中国剩余定理 的代码示例。

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(n, a):
    # n: list of moduli
    # a: list of remainders
    sum = 0
    prod = 1
    for ni in n:
        prod = ni
    for ni, ai in zip(n, a):
        pi = prod // ni
        mi = modinv(pi, ni)
        sum += ai  mi  pi
    return sum % prod
Example
n = [3, 5, 7]
a = [2, 3, 2]
print(chinese_remainder_theorem(n, a))  # Output: 23
                    

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll extended_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll d = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1  (a / b);
    return d;
}
ll modinv(ll a, ll m) {
    ll x, y;
    ll g = extended_gcd(a, m, x, y);
    if (g != 1) return -1;
    return (x % m + m) % m;
}
ll chinese_remainder_theorem(const vector<ll>& n, const vector<ll>& a) {
    ll prod = 1;
    for (ll ni : n) prod = ni;
    ll sum = 0;
    for (size_t i = 0; i < n.size(); ++i) {
        ll pi = prod / n[i];
        ll mi = modinv(pi, n[i]);
        sum = (sum + a[i]  mi % prod  pi % prod) % prod;
    }
    return sum;
}
int main() {
    vector<ll> n = {3, 5, 7};
    vector<ll> a = {2, 3, 2};
    cout << chinese_remainder_theorem(n, a) << endl; // Output: 23
    return 0;
}
                    

import java.util.;
public class CRT {
    public static long modInverse(long a, long m) {
        long m0 = m;
        long y = 0, x = 1;
        if (m == 1) return 0;
        while (a > 1) {
            long q = a / m;
            long t = m;
            m = a % m;
            a = t;
            t = y;
            y = x - q  y;
            x = t;
        }
        if (x < 0) x += m0;
        return x;
    }
    public static long chineseRemainderTheorem(long[] n, long[] a) {
        long prod = 1;
        for (long ni : n) prod = ni;
        long sum = 0;
        for (int i = 0; i < n.length; i++) {
            long pi = prod / n[i];
            long mi = modInverse(pi, n[i]);
            sum = (sum + a[i]  mi % prod  pi % prod) % prod;
        }
        return sum;
    }
    public static void main(String[] args) {
        long[] n = {3, 5, 7};
        long[] a = {2, 3, 2};
        System.out.println(chineseRemainderTheorem(n, a)); // Output: 23
    }
}
                    

🚀 应用场景：从数论到密码学

中国剩余定理不仅仅是一个数学游戏，它在现代科技中扮演着关键角色。以下是几个主要应用领域：

🌐 网友们还关心：CRT 与日常生活的联系

虽然 中国剩余定理听起来非常抽象，但它实际上保护着你的每一次在线支付。当你使用支付宝或微信支付时，底层的加密协议往往依赖于 RSA 或 ECC 等算法，而这些算法的效率优化中，中国剩余定理的身影随处可见。此外，在分布式系统中，CRT 也用于数据分片和校验，确保数据的可靠存储。

❓ 常见问题解答 (FAQ)

🔗 延伸阅读：数论中的其他瑰宝

如果您对 中国剩余定理感兴趣，您可能还会喜欢以下相关知识点：

• 费马小定理： 用于快速判断素数和求模逆元。
• 欧拉定理： 费马小定理的推广，适用于任意模数。
• 威尔逊定理： 用于素数检测的充要条件。
• 二次互反律： 数论中的明珠，描述二次剩余的关系。
• 离散对数问题： 椭圆曲线密码学的基础。