# 算法与数论讲义：同余 (Congruence)

## 1. 同余的定义

### 1.1 基本定义
设 $m$ 是正整数，若 $a$ 和 $b$ 是两个整数，且满足 $a - b$ 能被 $m$ 整除（即 $m \mid (a-b)$），则称 **$a$ 与 $b$ 模 $m$ 同余**。

**记作：**
$$a \equiv b \pmod m$$

### 1.2 余数定义
如果 $a$ 除以 $m$ 得余数 $r$，则 $a \equiv r \pmod m$。其中 $0 \le r < m$。
*例如：* $17 \div 5 = 3 \dots 2$，所以 $17 \equiv 2 \pmod 5$。

---

## 2. 同余关系的性质

同余关系是一种**等价关系**，具有以下三大核心性质：

1.  **自反性**：$a \equiv a \pmod m$。
2.  **对称性**：若 $a \equiv b \pmod m$，则 $b \equiv a \pmod m$。
3.  **传递性**：若 $a \equiv b \pmod m$ 且 $b \equiv c \pmod m$，则 $a \equiv c \pmod m$。

---

## 3. 同余式的运算性质

设 $a \equiv b \pmod m$，$c \equiv d \pmod m$，则有：

### 3.1 线性运算
1.  **加法**：$a + c \equiv b + d \pmod m$
2.  **减法**：$a - c \equiv b - d \pmod m$
3.  **乘法**：$a \cdot c \equiv b \cdot d \pmod m$

### 3.2 幂运算
如果 $a \equiv b \pmod m$，则对于任意正整数 $k$：
$$a^k \equiv b^k \pmod m$$
*注意：该性质在计算大数的最后一位或余数时极其有用。*

### 3.3 除法（特殊限制）
若 $ac \equiv bc \pmod m$，**不能**直接得出 $a \equiv b \pmod m$。
只有当 $\gcd(c, m) = 1$（即 $c$ 与 $m$ 互质）时，才能得出 $a \equiv b \pmod m$。

---

## 4. 数学应用举例

### 示例 1：计算大数余数
**问题：** 求 $3^{2024}$ 除以 $8$ 的余数。
**解：**
1.  我们知道 $3^2 = 9$。
2.  因为 $9 \equiv 1 \pmod 8$。
3.  根据幂运算性质：$(3^2)^{1012} \equiv 1^{1012} \pmod 8$。
4.  即 $3^{2024} \equiv 1 \pmod 8$。
**结论：** 余数为 $1$。

### 示例 2：整除性判断
**问题：** 证明一个数能被 $9$ 整除，当且仅当它的各位数字之和能被 $9$ 整除。
**证明：**
1.  任一整数 $n$ 可表示为 $a_k 10^k + \dots + a_1 10^1 + a_0$。
2.  因为 $10 \equiv 1 \pmod 9$，所以 $10^i \equiv 1^i \equiv 1 \pmod 9$。
3.  因此 $n \equiv a_k(1) + \dots + a_1(1) + a_0 \pmod 9$。
4.  $n \equiv \sum a_i \pmod 9$。
**结论：** 数字本身与它的各位数之和模 9 同余。

---

## 5. 生活与工程应用

### 5.1 星期计算（周期问题）
**问题：** 如果今天星期一，过 $10^{10}$ 天后是星期几？
**解析：**
一星期 7 天是一个周期。我们求 $10^{10} \pmod 7$。
1.  $10 \equiv 3 \pmod 7$。
2.  $10^{10} \equiv 3^{10} \pmod 7$。
3.  $3^{10} = (3^3)^3 \cdot 3 = 27^3 \cdot 3$。
4.  因为 $27 \equiv -1 \pmod 7$，所以 $27^3 \equiv (-1)^3 \equiv -1 \pmod 7$。
5.  结果为 $-1 \cdot 3 = -3$。
6.  $-3 \equiv 4 \pmod 7$。
**结论：** 星期一往后数 4 天，是星期五。

### 5.2 校验码设计 (Check Digit)
我们的身份证号最后一位（如果是 X 则代表 10）或者是 ISO 国际标准书号（ISBN）都利用了同余。
*   **身份证校验**：将前 17 位数字加权求和，然后模 11，根据余数决定第 18 位。这可以自动检测录入时的笔误。

### 5.3 密码学 (RSA算法)
现代互联网安全的基石 RSA 加密算法，其核心就是高次幂的同余运算：
$$C = M^e \bmod n$$
只有知道特定密钥的人才能通过同余方程解出原始信息 $M$。

---

## 6. 代码实现（Python 示例）

在计算机中，我们经常需要处理负数的取模，或者大数幂取模。

```python
# 1. 基础取模
a = 17
m = 5
print(f"{a} % {m} = {a % m}") # 输出 2

# 2. 负数取模 (Python的 % 结果符号随除数)
# -1 mod 7 在数学上通常认为是 6
print(f"-1 % 7 = {-1 % 7}") # 输出 6

# 3. 快速幂取模 (计算 3^2024 % 8)
# pow(base, exp, mod) 函数非常高效
result = pow(3, 2024, 8)
print(f"3^2024 mod 8 = {result}") # 输出 1
```

---

## 7. 总结

同余不仅是纯数学中的一个符号，它本质上是**对周期的抽象**。
*   在**数学**中，它简化了超大数字的运算。
*   在**计算机**中，它确保了溢出处理和散列表（Hash）的分布。
*   在**生活中**，它管理着时间、周期和数据的准确性。

算法与数论讲义：同余 (Congruence)

1. 同余的定义

1.1 基本定义

设 $m$ 是正整数，若 $a$ 和 $b$ 是两个整数，且满足 $a - b$ 能被 $m$ 整除（即 $m \mid (a-b)$），则称 $a$ 与 $b$ 模 $m$ 同余。

记作： $$a \equiv b \pmod m$$

1.2 余数定义

如果 $a$ 除以 $m$ 得余数 $r$，则 $a \equiv r \pmod m$。其中 $0 \le r < m$。 例如： $17 \div 5 = 3 \dots 2$，所以 $17 \equiv 2 \pmod 5$。

2. 同余关系的性质

同余关系是一种等价关系，具有以下三大核心性质：

自反性：$a \equiv a \pmod m$。
对称性：若 $a \equiv b \pmod m$，则 $b \equiv a \pmod m$。
传递性：若 $a \equiv b \pmod m$ 且 $b \equiv c \pmod m$，则 $a \equiv c \pmod m$。

3. 同余式的运算性质

设 $a \equiv b \pmod m$，$c \equiv d \pmod m$，则有：

3.1 线性运算

加法：$a + c \equiv b + d \pmod m$
减法：$a - c \equiv b - d \pmod m$
乘法：$a \cdot c \equiv b \cdot d \pmod m$

3.2 幂运算

如果 $a \equiv b \pmod m$，则对于任意正整数 $k$： $$a^k \equiv b^k \pmod m$$ 注意：该性质在计算大数的最后一位或余数时极其有用。

3.3 除法（特殊限制）

若 $ac \equiv bc \pmod m$，不能直接得出 $a \equiv b \pmod m$。只有当 $\gcd(c, m) = 1$（即 $c$ 与 $m$ 互质）时，才能得出 $a \equiv b \pmod m$。

4. 数学应用举例

示例 1：计算大数余数

问题： 求 $3^{2024}$ 除以 $8$ 的余数。解： 1. 我们知道 $3^2 = 9$。 2. 因为 $9 \equiv 1 \pmod 8$。 3. 根据幂运算性质：$(3^2)^{1012} \equiv 1^{1012} \pmod 8$。 4. 即 $3^{2024} \equiv 1 \pmod 8$。 结论： 余数为 $1$。

示例 2：整除性判断

问题： 证明一个数能被 $9$ 整除，当且仅当它的各位数字之和能被 $9$ 整除。 证明： 1. 任一整数 $n$ 可表示为 $a_k 10^k + \dots + a_1 10^1 + a_0$。 2. 因为 $10 \equiv 1 \pmod 9$，所以 $10^i \equiv 1^i \equiv 1 \pmod 9$。 3. 因此 $n \equiv a_k(1) + \dots + a_1(1) + a_0 \pmod 9$。 4. $n \equiv \sum a_i \pmod 9$。 结论： 数字本身与它的各位数之和模 9 同余。

5. 生活与工程应用

5.1 星期计算（周期问题）

问题： 如果今天星期一，过 $10^{10}$ 天后是星期几？ 解析： 一星期 7 天是一个周期。我们求 $10^{10} \pmod 7$。 1. $10 \equiv 3 \pmod 7$。 2. $10^{10} \equiv 3^{10} \pmod 7$。 3. $3^{10} = (3^3)^3 \cdot 3 = 27^3 \cdot 3$。 4. 因为 $27 \equiv -1 \pmod 7$，所以 $27^3 \equiv (-1)^3 \equiv -1 \pmod 7$。 5. 结果为 $-1 \cdot 3 = -3$。 6. $-3 \equiv 4 \pmod 7$。 结论： 星期一往后数 4 天，是星期五。

5.2 校验码设计 (Check Digit)

我们的身份证号最后一位（如果是 X 则代表 10）或者是 ISO 国际标准书号（ISBN）都利用了同余。 * 身份证校验：将前 17 位数字加权求和，然后模 11，根据余数决定第 18 位。这可以自动检测录入时的笔误。

5.3 密码学 (RSA算法)

现代互联网安全的基石 RSA 加密算法，其核心就是高次幂的同余运算： $$C = M^e \bmod n$$ 只有知道特定密钥的人才能通过同余方程解出原始信息 $M$。

6. 代码实现（Python 示例）

在计算机中，我们经常需要处理负数的取模，或者大数幂取模。

# 1. 基础取模
a = 17
m = 5
print(f"{a} % {m} = {a % m}") # 输出 2

# 2. 负数取模 (Python的 % 结果符号随除数)
# -1 mod 7 在数学上通常认为是 6
print(f"-1 % 7 = {-1 % 7}") # 输出 6

# 3. 快速幂取模 (计算 3^2024 % 8)
# pow(base, exp, mod) 函数非常高效
result = pow(3, 2024, 8)
print(f"3^2024 mod 8 = {result}") # 输出 1

7. 总结

同余不仅是纯数学中的一个符号，它本质上是对周期的抽象。 * 在数学中，它简化了超大数字的运算。 * 在计算机中，它确保了溢出处理和散列表（Hash）的分布。 * 在生活中，它管理着时间、周期和数据的准确性。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com