同余与同余方程

探索模运算世界的交互式可视化教程

一、同余定义与直观演示

同余关系的定义

在数论中，同余关系是一种基本的等价关系。如果两个整数 a 和 b 除以同一个正整数 n 所得到的余数相同，那么我们就称 a 和 b 对于模 n 同余。

其数学符号表示为：

a ≡ b (mod n)

这等价于说：n 能够整除 a 与 b 的差，即 (a - b) 是 n 的整数倍。

试一试：

整数 a：

整数 b：

模数 n (n ≥ 2)：

数轴表示

模环表示

数轴可视化

在数轴上，同余的数落在模 n 的相同“位置”上。

说明：数轴上标记了 0 到 n-1 的位置点。如果 a 和 b 同余，它们将被映射到同一个高亮的位置点。

模环可视化

想象一个有 n 个刻度的时钟。同余的数会指向时钟上的同一点。

说明：圆环上均匀分布着 0 到 n-1 的点。如果 a 和 b 同余，代表它们的指针会指向同一个高亮的点。

请点击“演示同余关系”按钮查看结果。

二、同余性质与运算规则

同余关系具有类似等式的良好性质，这使得模运算非常有用。

加法同余

如果 a₁ ≡ b₁ (mod n) 且 a₂ ≡ b₂ (mod n)，那么：

a₁ + a₂ ≡ b₁ + b₂ (mod n)

例如 (mod 5)： 7 ≡ 2, 8 ≡ 3 ⇒ 7+8 = 15 ≡ 0, 2+3 = 5 ≡ 0.

减法同余

如果 a₁ ≡ b₁ (mod n) 且 a₂ ≡ b₂ (mod n)，那么：

a₁ - a₂ ≡ b₁ - b₂ (mod n)

例如 (mod 5)： 17 ≡ 2, 8 ≡ 3 ⇒ 17-8 = 9 ≡ 4, 2-3 = -1 ≡ 4.

乘法同余

如果 a₁ ≡ b₁ (mod n) 且 a₂ ≡ b₂ (mod n)，那么：

a₁ · a₂ ≡ b₁ · b₂ (mod n)

例如 (mod 5)： 7 ≡ 2, 8 ≡ 3 ⇒ 7×8 = 56 ≡ 1, 2×3 = 6 ≡ 1.

幂运算同余

如果 a ≡ b (mod n)，那么对于任意正整数 k：

a^k ≡ b^k (mod n)

例如 (mod 5)： 7 ≡ 2 ⇒ 7³=343 ≡ 3, 2³=8 ≡ 3.

传递性

如果 a ≡ b (mod n) 且 b ≡ c (mod n)，那么：

a ≡ c (mod n)

例如 (mod 3)： 8 ≡ 2, 2 ≡ 5 ⇒ 8 ≡ 5.

数乘性质

如果 a ≡ b (mod n)，那么对于任意整数 c：

a · c ≡ b · c (mod n)

例如 (mod 4)： 7 ≡ 3, c=5 ⇒ 7×5=35 ≡ 3, 3×5=15 ≡ 3.

性质演示器

选择一个性质，输入满足前提条件的数值，观察结论是否成立。

选择要演示的性质：

模数 n (n ≥ 2)：

三、一元一次同余方程求解

方程形式

一元一次同余方程是最基本的一种同余方程，其一般形式为：

a ⋅ x ≡ b (mod n)

其中 a, b, n 是已知的整数 (n > 1)，而 x 是我们要求解的未知整数。

求解的关键：最大公约数 (GCD)

该方程有解的充要条件是：a 和 n 的最大公约数 d = gcd(a, n) 必须能够整除 b（记作 d | b）。

如果 d 不能整除 b，则方程无解。
如果 d 能整除 b，则方程恰好有 d 个模 n 意义下不同的解。这些解构成一个模 n/d 的完全剩余系。

求解示例：

输入方程 a ⋅ x ≡ b (mod n) 的系数：

系数 a：

常数项 b：

模数 n (n ≥ 2)：

C++ 实现：求解一元一次同余方程

下面是用 C++ 实现求解 ax ≡ b (mod n) 的核心代码，包括扩展欧几里得算法。

// C++ 代码实现求解同余方程 ax = b (mod n)

#include 
#include 
#include  // 为了 std::gcd (C++17)

// 扩展欧几里得算法
// 计算 ax + by = gcd(a, b)，并返回 gcd(a, b)
// x 和 y 是通过引用传递的解
long long extendedGCD(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long d = extendedGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return d;
}

// 求解线性同余方程 ax ≡ b (mod n)
// 返回一个包含所有解 (mod n) 的 vector，如果无解则返回空 vector
std::vector<long long> solveLinearCongruence(long long a, long long b, long long n) {
    long long x, y;
    // 使用 C++17 的 std::gcd，或者自己实现 gcd 函数
    // long long d = std::gcd(a, n); // 需要 #include  且 C++17
    long long d = extendedGCD(a, n, x, y); // 同时计算 gcd 和 x, y

    std::vector<long long> solutions;

    if (b % d != 0) {
        // 无解条件: gcd(a, n) 不能整除 b
        return solutions; // 返回空 vector
    }

    // 方程有解，计算一个特解 x0
    // ax + ny = d  =>  (a/d)x + (n/d)y = 1
    // x 是 a 关于 n 的某个“伪逆元”乘以 d
    // x * (a/d) ≡ 1 (mod n/d)
    // 一个特解 x0 = x * (b/d) mod (n/d)

    long long n_prime = n / d;
    // 确保 x 是正数，并且计算特解
    long long x0 = (x % n_prime + n_prime) % n_prime; // 防止 x 是负数
    x0 = (x0 * (b / d)) % n_prime;

    // 计算所有 d 个解
    for (int i = 0; i < d; ++i) {
        solutions.push_back((x0 + i * n_prime) % n);
    }

    // 对解进行排序（可选）
    // std::sort(solutions.begin(), solutions.end());

    return solutions;
}

// 主函数示例
int main() {
    long long a = 6, b = 4, n = 8;
    std::cout << "求解方程: " << a << "x = " << b << " (mod " << n << ")" << std::endl;

    std::vector<long long> result = solveLinearCongruence(a, b, n);

    if (result.empty()) {
        std::cout << "方程无解。" << std::endl;
    } else {
        std::cout << "方程的解 (mod " << n << ") 为:" << std::endl;
        for (long long sol : result) {
            std::cout << sol << " ";
        }
        std::cout << std::endl;
        std::cout << "共有 " << result.size() << " 个解。" << std::endl;
    }

    return 0;
}

四、学习小贴士与拓展

误区 1：同余方程总是有解

错误！ 方程 ax ≡ b (mod n) 并非总有解。必须满足 gcd(a, n) 能整除 b 这个条件。

反例： 2x ≡ 1 (mod 4) 无解，因为 gcd(2, 4) = 2，而 2 不能整除 1。

误区 2：同余方程的解是唯一的

不一定！ 如果 d = gcd(a, n) > 1 且方程有解，那么它将有 d 个模 n 下不同的解。

例如： 4x ≡ 2 (mod 6)。这里 d = gcd(4, 6) = 2，2 能整除 2，所以有解。解为 x ≡ 2 (mod 3)，这对应于模 6 下的解 x ≡ 2 和 x ≡ 5，共 2 个解。

误区 3：随意进行除法运算

警惕！ 在模运算中，不能像普通代数那样随意进行除法。例如，4x ≡ 4 (mod 6) 不能直接两边除以 4 得到 x ≡ 1 (mod 6)。正确的解是 x ≡ 1 (mod 3) 或 x ≡ 4 (mod 3)，即 x ≡ 1, 4 (mod 6)。除法需要通过乘以“模逆元”来实现，但逆元不一定存在。

误区 4：混淆不同模数下的同余式

注意！ 比较或合并同余式时，必须确保它们的模数 n 是相同的。

例如： 5 ≡ 2 (mod 3) 和 5 ≡ 1 (mod 4) 都是正确的，但这并不意味着 2 和 1 在某个模下同余。

为什么会有 `d = gcd(a, n)` 个解？

当 d | b 时，方程 ax ≡ b (mod n) 等价于求解一个更简单的方程：

(a/d) ⋅ x ≡ (b/d) (mod n/d)

令 a' = a/d, b' = b/d, n' = n/d。新方程是 a'x ≡ b' (mod n')。

由于 gcd(a', n') = gcd(a/d, n/d) = gcd(a, n) / d = d / d = 1，a' 和 n' 互质。这意味着 a' 在模 n' 下存在唯一的模逆元，因此新方程有且仅有一个解，记作 x ≡ x₀ (mod n')。

这个解 x₀ 意味着所有满足 x = x₀ + k ⋅ n' （其中 k 为任意整数）的 x 都是新方程的解。

现在，我们要把这些解放回原模数 n 的背景下。在模 n 的意义下，哪些 x₀ + k ⋅ n' 是不同的呢？

考虑 k = 0, 1, 2, ..., d-1。对应的解是：

x₀, x₀ + n', x₀ + 2n', ..., x₀ + (d-1)n'

这些解在模 n 下都是不同的。因为如果 x₀ + i ⋅ n' ≡ x₀ + j ⋅ n' (mod n) 且 0 ≤ i < j < d，则 (j-i)n' 必须是 n 的倍数。但 n = d ⋅ n'，所以 (j-i)n' 是 dn' 的倍数，意味着 j-i 是 d 的倍数。然而 0 < j-i < d，这是不可能的。

当 k = d 时，x₀ + d ⋅ n' = x₀ + n ≡ x₀ (mod n)，解开始重复。

因此，恰好有 d 个模 n 下不同的解。

示例回顾：4x ≡ 2 (mod 6)

1. d = gcd(4, 6) = 2.

2. d | b (2 | 2) ✓.

3. 简化方程：(4/2)x ≡ (2/2) (mod 6/2) ⇒ 2x ≡ 1 (mod 3).

4. 求解 2x ≡ 1 (mod 3)。 2 的模 3 逆元是 2 (因为 2*2=4 ≡ 1 mod 3)。所以 x ≡ 1 * 2 ≡ 2 (mod 3)。 x₀ = 2。

5. n' = n/d = 6/2 = 3.

6. 两个解 (d=2) 是：

k=0: x₀ + 0*n' = 2 + 0*3 = 2. 解为 x ≡ 2 (mod 6).
k=1: x₀ + 1*n' = 2 + 1*3 = 5. 解为 x ≡ 5 (mod 6).

最终解集为 {2, 5} (mod 6)。

同余无处不在

日历计算： 计算星期几（模 7），判断闰年（涉及模 4, 100, 400）。例如，今天星期三，100 天后是星期几？ (100 mod 7 = 2)，所以是星期三 + 2天 = 星期五。
时钟算术： 12 小时制或 24 小时制就是模 12 或模 24 的运算。
校验码： 身份证号、ISBN 书号、银行卡号等的最后一位通常是校验码，使用模运算（如模 10 或模 11）来验证号码的有效性。
密码学： 现代密码学（如 RSA、ECC）严重依赖数论和模运算，特别是大素数的模幂运算和离散对数问题。
计算机科学： 哈希函数（Hash Function）常用模运算将大范围的输入映射到小范围的索引；伪随机数生成器也常用线性同余法。
数据编码： 循环冗余校验 (CRC) 等错误检测码基于多项式模运算。

趣味例子：报数游戏

一群人围成一圈报数，从 1 报到 m，报到 m 的人出局，然后从下一个人继续从 1 开始报数，直到剩下最后一个人。这个问题（约瑟夫环问题）的解可以通过模运算来分析。

简介：解同余方程组

中国剩余定理 (Chinese Remainder Theorem, CRT) 提供了一种求解一元线性同余方程组的方法。

该定理最初记载于中国古代数学著作《孙子算经》中，形式如下：

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

用现代数学语言描述，就是求解同余方程组：

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

CRT 告诉我们，如果模数 n₁, n₂, ..., n<0xE2><0x82><0x99> 两两互质，那么形如：

x ≡ a₁ (mod n₁)
x ≡ a₂ (mod n₂)
...
x ≡ a<0xE2><0x82><0x99> (mod n<0xE2><0x82><0x99>)

的同余方程组，在模 N = n₁ × n₂ × ... × n<0xE2><0x82><0x99> 的意义下有唯一解。

CRT 不仅有理论价值，在密码学、编码理论和计算机算法中都有重要应用。

这是一个更进阶的主题，通常在学习了基础同余方程和模逆元之后进行探讨。你可以搜索“中国剩余定理详解”来深入学习它的解法和证明。

一、同余定义与直观演示

同余关系的定义

试一试：

数轴可视化

模环可视化

二、同余性质与运算规则

加法同余

减法同余

乘法同余

幂运算同余

传递性

数乘性质

性质演示器

演示过程与结果：

三、一元一次同余方程求解

方程形式

求解的关键：最大公约数 (GCD)

求解示例：

C++ 实现：求解一元一次同余方程

四、学习小贴士与拓展

误区 1：同余方程总是有解

误区 2：同余方程的解是唯一的

误区 3：随意进行除法运算

误区 4：混淆不同模数下的同余式

为什么会有 d = gcd(a, n) 个解？

示例回顾：4x ≡ 2 (mod 6)

同余无处不在

趣味例子：报数游戏

简介：解同余方程组

为什么会有 `d = gcd(a, n)` 个解？