2026年高中数学《数论：概念和问题》 讲义

2026年高中数学《数论：概念和问题》 讲义 第一章 整除 第一章比较初等, 讨论了整除的性质、同余和带余除法. 这些概念后续经常用到, 代表了算术的基础, 更深入的内容后续在此之上建立. 我们会更多地使用非标准的例子或应用, 其中一些是非平凡的 (例如有限差分和同余方面的应用). 本书中的变量,如没有明显指出,可以默认是正整数,总是用 表示正整数的集合. 1.1 基本性质 这一节我们引入整除的概念, 学习一些基本性质. 1.1.1 整除和同余 我们从整除关系的定义开始. 定义 1.1. 设 是整数. 如果存在整数 ,满足 ,则我们说 整除 并记作 . 有很多表示 整除 的等价方法: 可以说 被 整除; 可以说 是 的因子; 可以说 是 的倍数. 这些说法在实践中都经常使用. 注意若 ,则说 整除 等价于说有理数 是一个整数. 而上面的定义也包含了 的情形,这时 0整除 当且仅当 . 还可以说,每个整数都是 0 的一个因子,而 0 的倍数只有 0 . 如果 2 整除整数 ,则说 是一个偶数,否则说 是一个奇数. 偶数有 , ,而奇数有 . 若 是奇数,则 是偶数. 每个整数 或者写成 或者写成 的形式,其中 是某个整数. 特别可以得到,两个相邻整数的乘积总是偶数. 如果 是奇数,比如说 , 则 是 8 的倍数. 因此每个完全平方数(就是 形式的数, 是整数)或者是 4 的倍数或者是 形式的数. 下面的结果总结了整除关系的基本性质. 命题 1.2. 整除关系有如下性质: (a) (反射性) 对所有整数 整除 . (b) (传递性) 若 ,并且 ,则 . (c) 若 是整数,并且 ,则 对所有整数 成立. (d) 若 ,并且 ,则 . (e) 若 ,并且 ,则 . 证: 所有的性质可以直接从定义出发证明. 我们这里仅仅证明性质(c)和(e), 其他的请读者完成. 对性质 (c),记 ,其中 是某整数. 则 是 的倍数. 对性质(e),记 ,其中 是整数. 则 所以 . 我们接下来介绍一个关键的记号和定义———同余: 定义 1.3. 设 是整数,若 ,则我们说 和 模 同余,并且记作 下面定理的多数部分是命题 1.2 的重述, 这些在实际计算中常常使用. 定理 1.4. 对所有的整数 ,我们有: (a) (反射性) . (b) (对称性) 若 ,则 . (c) (传递性) 若 ,且 ,则 . (d) 若 ,且 ,则 ,并且 (e) 若 ,则 . 反之,若 ,且 ,则 . 证: 或者显然,或者是命题 1.2 的直接结论. 性质(e)可以直接从定义得到, 留给读者. 注释 1.5. 在同余式中消去律不总是成立,也就是说当 时,不总是有 或者 . 例如 ,但是 2 和 0 模 4 并不同余. 在后面我们会看到,当 和 的公因子只有 时,确实可以在同余式 中 “消去 ”. 我们用具体的题目说明一下同余符号在整除性问题中的应用. 例 1.6. 求 的最后一位数字. 证: 我们有 所以, 最后一位数字是 3 . 例 1.7. 证明: 对任何 ,整数 能被 133 整除. 证: 因为 ,所以 例 1.8. (Kvant 274) 分别求具有下列形式的最小数: (a) ; (b) ; (c) , 其中 和 都是正整数. 证:(a) 的末位数只能是 6 或 4 ,因此具有形式 的数最小是 4 . 而 ,所以答案是 4 . (b) 首先有 ,接下来我们证明这就是最小的数. 假设对某 和 ,有 . 因为 ,所以 或者 . 前者不可能,因为会得到 ; 后者也不可能, 因为会得到 . (c) 首先看到,这样的数都是 4 的倍数,因为 和 都模 4 余 1 . 我们证明最小的数是 . 注意到 . 所以 ,因此 . 下面的基本定理很常用. 定理 1.9. (a) 若 是整数,则 对所有 成立. (b) 更一般地,若 是正整数,满足 ,则 对所有整数 成立. 若 是奇数,则 对所有整数 成立. 特别地,若 是奇数,则 对所有整数 成立. 证:(a) 可以直接从下面的恒等式得到 (b) 设 是某正整数,记 ,则只需证明 (可由(a)得到). 当 是奇数时, 可以从下式得到 注释 1.10. (a) 后面我们会看到,在一些较弱的假设下,由整除关系 可以得到 . (b) 恒等式 是一个非常基本的公式, 在书中会经常用到. 在很多情形下, 定理 1.9 已足够使用；在某些情形下, ... ...