M 数论与组合

📋 模块概览

对应考纲 Section 1: MM1.1, MM2.4, M2.3, M2.5 对应 Paper: P2 重点（逻辑推理与证明验证） 建议课时: 1 课时 | 目标题量: 8 题

M1 整除与余数 [MM1.1, M2.3]

M1.1 整除的基本概念

整除：若存在整数 $k$ 使得 $a = bk$，则称 $b$ 整除 $a$，记作 $b \mid a$。

⚠️ 常见误解：整除关系不具有传递性的特殊形式。例如若 $a \mid bc$，不一定推出 $a \mid b$ 或 $a \mid c$。

反例：$a = 6$, $b = 2$, $c = 3$。$6 \mid 6$，但 $6 \nmid 2$ 且 $6 \nmid 3$。

M1.2 带余除法

对于整数 $a$ 和正整数 $b$，存在唯一整数 $q$（商）和 $r$（余数），使得：

⚠️ 关键陷阱：余数 $r$ 必须严格小于除数 $b$。当两个余数相乘时，乘积可能超过除数，此时真正的余数是 $rs \bmod b$，而非 $rs$ 本身。

经典错误示例： 设 $b$ 除以 $a$ 的余数为 $r$，$c$ 除以 $a$ 的余数为 $s$。若 $r, s > 0$，能否推出 $bc$ 除以 $a$ 的余数是 $rs$？

错误：例如 $a = 6$, $r = 2$, $s = 3$，则 $rs = 6$，正好等于 $a$，此时 $bc$ 能被 $a$ 整除（余数为 $0$），而非余数为 $6$。

M1.3 质数与质因数分解

质数：大于 $1$ 且只有 $1$ 和自身两个正因数的整数。

唯一分解定理：每个大于 $1$ 的整数都能唯一分解为质数的乘积。

应用：判断整除、求最大公因数、判断质数个数。

M2 排列组合基础 [M2.5]

M2.1 基本计数原理

乘法原理：若任务 $A$ 有 $m$ 种完成方式，对于每种方式，任务 $B$ 有 $n$ 种完成方式，则完成 $A$ 和 $B$ 共有 $m \times n$ 种方式。

鸽巢原理：若将 $n+1$ 个物品放入 $n$ 个盒子，则至少有一个盒子包含至少 $2$ 个物品。

⚠️ 应用场景：

• 圆桌座位问题：控制空隙，使后来者必相邻
• 配对问题：从有序集合中选取若干项，保证存在某对满足条件

M2.2 Dyck 路径（山峰编码问题）

定义：由 $n$ 个上坡（U）和 $n$ 个下坡（D）组成的路径，从高度 $0$ 出发、回到高度 $0$，且过程中不低于高度 $0$。

有效编码的特征：

• 第一个字符必为 U
• 最后一个字符必为 D
• 任意位置处累计的 U 数量不少于累计的 D 数量

变换验证技巧：

• 反转操作：首字母变为 D → 无效
• U-D 互换：首字母变为 D → 无效
• 开头加 U、结尾加 D：整体抬高一层 → 有效

计数公式（Catalan 数）：阶数为 $n$ 的有效编码数量为

M2.3 配对与鸽巢原理应用

策略：

1. 找出所有满足特定条件的配对
2. 确定孤立项（不参与配对的项）
3. 计算最大安全选择数：孤立项数 + 配对数
4. 答案 = 安全数 + 1

M3 二项式系数性质 [MM2.4]

M3.1 二项式系数定义

表示从 $n$ 个物品中选取 $k$ 个的方式数。

M3.2 整除性分析

判断 $\binom{n}{k} a^{n-k} b^k$ 能否被某数 $m$ 整除时，需考察：

• $\binom{n}{k}$ 的质因数分解
• $a^{n-k}$ 和 $b^k$ 的贡献

技巧：若 $m = p^e q^f$（质因数分解），则系数需同时满足：

• 含至少 $e$ 个因子 $p$
• 含至少 $f$ 个因子 $q$

常见错误：忽略二项式系数本身的质因数贡献，只看 $a$ 和 $b$ 的幂次。

⚡ 速解技巧汇总

⚠️ 易错警示

• ❌ 若 $a \mid bc$，不一定有 $a \mid b$ 或 $a \mid c$
• ❌ 余数相乘后可能超过除数，不能直接当作新余数
• ❌ Dyck 路径反转后首字母变为 D，失去有效性
• ❌ 二项式系数整除性判断时，需同时检查质因数的多个贡献来源

📝 精选例题

例题 1（2016 P2 Q13 · 整除性证明错误）

题目：在以下对错误命题的证明中，哪一行包含错误？

命题：若 $a$ 整除 $bc$，则 $a$ 整除 $b$ 或 $a$ 整除 $c$。

证明步骤：

1. 逆否命题转换
2. 设余数 $r, s$，其中 $0 < r, s < a$
3. $b = ax + r$, $c = ay + s$
4. $bc = a(axy + xs + yr) + rs$
5. $bc$ 除以 $a$ 的余数是 $rs$
6. $rs > 0$，故 $a$ 不整除 $bc$

题目分析 本题考查整除性的逻辑推理。需逐行审查证明过程，识别哪一步推导出错。

解题步骤 第1-4行均正确。

第5行断言 $bc$ 除以 $a$ 的余数是 $rs$，这是错误所在。

当 $rs \ge a$ 时，$rs$ 并非余数。例如 $a = 6$, $r = 2$, $s = 3$： $rs = 6 = a$

此时 $bc$ 除以 $a$ 的余数为 $0$（即 $a$ 整除 $bc$），而非余数为 $6$。

反例 $a = 6$, $b = 2$, $c = 3$：

• $6 \mid bc$（因为 $bc = 6$）
• 但 $6 \nmid 2$ 且 $6 \nmid 3$

证明试图用余数论证逆命题，却在第5行忽略了余数乘积可能超过除数的情形。

快捷思路 直接构造反例：$a = 6$, $r = 2$, $s = 3$，则 $rs = 6 = a$，余数应为 $0$。第5行的断言在反例下失效。

正确答案E（第5行）

知识点Number Theory | 考纲: MM1.1, M2.3

例题 2（2018 P2 Q8 · Dyck 路径变换）

题目：山峰剖面图的有效编码由 $n$ 个 U 和 $n$ 个 D 组成，从海平面出发回到海平面，且不低于海平面。判断以下三种变换是否保持有效性：

I. 反转编码 II. 将每个 U 替换为 D，每个 D 替换为 U III. 在开头加 U，结尾加 D

题目分析 本题考查 Dyck 路径的性质。有效编码必须首字母为 U、尾字母为 D，且任意位置累计 U 数不少于累计 D 数。

解题步骤 判断 I：反转编码。

原编码以 D 结尾，反转后以 D 开头。第一个字符为 D 时，第一步就走低于海平面，故反转后不是有效编码。I 错误。

判断 II：U-D 互换。

原编码以 U 开头，互换后以 D 开头。同样第一步就低于海平面，故互换后不是有效编码。II 错误。

判断 III：开头加 U、结尾加 D。

新编码首字母为 U，满足基本条件。原编码全程不低于海平面，新编码将原路径整体抬高一层（高度从 $0$ 提升到 $1$），更不会低于海平面。最后加的 D 使高度回到 $0$。新编码有 $n+1$ 个 U 和 $n+1$ 个 D，满足所有条件。III 正确。

快捷思路 抓住核心约束：首字母必为 U。I 和 II 都使首字母变为 D，立判无效。III 开头加 U 保持首字母为 U，且全程抬高一层，天然有效。

正确答案D（仅 III 正确）

知识点Combinatorics | 考纲: M2.5

🏋️ 课后练习（限时 10 分钟）

完整解析见题库数据库，每题均含解题步骤与快捷思路。

附录：典型题型总结

题型 A：整除性证明验证

特征：给出一个对命题的证明过程，要求识别哪一步出错。

策略：

1. 逐行审查每一步的逻辑合法性
2. 特别关注除法操作（可能丢根）、余数操作（可能超限）
3. 用具体反例验证可疑步骤

题型 B：鸽巢原理应用

特征：圆形排列或配对问题，求保证某条件成立的最小数量。

策略：

1. 确定控制量：空隙数、配对数、孤立项数
2. 构造最坏情况（让条件最难满足）
3. 计算安全边界，答案 = 安全数 + 1

题型 C：二项式系数性质

特征：判断展开式中哪些项的系数满足整除性条件。

策略：

1. 分析目标数的质因数分解
2. 检验首尾两项（常为边界情况）
3. 中间项往往自动满足，无需逐一验证

讲义完成！本模块共 8 题，覆盖数论基础与组合计数两大主题。