K Number Theory and Combinatorics

模块 K：数论与组合

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

📋 模块概览

小节	内容	对应考纲	历年真题频率	课时
K1	整除与余数	MM1.1, M2.3	8 年 3 次	0.4
K2	排列组合基础	M2.5	8 年 3 次	0.3
K3	二项式系数性质	MM2.4	8 年 2 次	0.3

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

1.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$ 。

1.2 带余除法

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

$a = bq + r, \quad 0 \le r < b$

⚠️ 关键陷阱：余数 $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$ 。

1.3 质数与质因数分解

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

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

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

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

2.1 基本计数原理

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

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

⚠️ 应用场景：

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

2.2 Dyck 路径（山峰编码问题）

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

有效编码的特征：

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

变换验证技巧：

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

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

$C_n = \frac{1}{n+1}\binom{2n}{n}$

2.3 配对与鸽巢原理应用

策略：

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

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

3.1 二项式系数定义

$\binom{n}{k} = \frac{n!}{k!(n-k)!}$

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

3.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$ 的幂次。

⚡ 速解技巧汇总

场景	技巧
余数乘积问题	检验 $rs$ 是否超过除数，真正余数是 $rs \bmod a$
圆桌座位问题	每两人间最多空 $k$ 个座位，总数 $\div$ (人+空)向上取整
Dyck 路径变换	检验首字母是否为 U，不满足即无效
配对问题	统计配对数和孤立项数，安全数 = 孤立 + 配对
二项式整除性	先检验首尾两项，中间项常自动满足条件

⚠️ 易错警示

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

📝 精选例题

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

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

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

证明步骤：

逆否命题转换
设余数 $r, s$ ，其中 $0 < r, s < a$
$b = ax + r$ , $c = ay + s$
$bc = a(axy + xs + yr) + rs$
$bc$ 除以 $a$ 的余数是 $rs$
$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 分钟）

#	题号	考点	对应考纲	难度
1	2016 P2 Q20	正多边形内角方程	MM1.1	⭐⭐⭐
2	2017 P2 Q13	标准形式加法进位	M2.3	⭐⭐⭐
3	2017 P2 Q20	排列组合推理	M2.5	⭐⭐⭐⭐
4	2019 P2 Q9	鸽巢原理圆桌问题	M2.5	⭐⭐⭐
5	2022 P2 Q8	配对与鸽巢原理	M2.5	⭐⭐⭐
6	2023 P1 Q6	二项式系数整除性	MM2.4	⭐⭐⭐

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

附录：典型题型总结

题型 A：整除性证明验证

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

策略：

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

题型 B：鸽巢原理应用

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

策略：

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

题型 C：二项式系数性质

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

策略：

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

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