2026年高中数学《数论：概念和问题》 讲义
文档属性
| 名称 | 2026年高中数学《数论：概念和问题》 讲义 |
|
|
| 格式 | docx | ||
| 文件大小 | 63.6KB | ||
| 资源类型 | 教案 | ||
| 版本资源 | 人教A版（2019） | ||
| 科目 | 数学 | ||
| 更新时间 | 2026-01-16 00:00:00 | ||
图片预览
文档简介
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 已足够使用；在某些情形下,需要对 进行更细致的分析.
下面的结果是定理 1.9 用同余式语言的描述.
推论 1.11. 设 是整数, 是正整数, 是 的正因子:
(a) 若 ,则 .
(b) 若 ,则 .
(c) 若 ,且 是奇数,则 .
例 1.12. 利用 ,证明: .
证: 首先有 ,所以 . 而 , 所以 . 因此 . 正是我们需要的.
例 1.13. (a) 证明: 正整数 和它在十进制下数码和的差被 9 整除.
(b) 设 是正整数, 分别是 在十进制下奇数位和偶数位上的数码和 ( 的最后一位为第 0 位). 证明: .
证: (a) 记
其中 是十进制下的数码, . 则
是 9 的倍数, 因为根据定理 1.9, 每一个 10 的幂减 1 是 9 的倍数.
(b) 证明和(a)相同,关键是 对所有 成立.
例 1.14. (Kvant 676) 证明: 对所有的正整数 的数码和不小于 19.
证: 用 表示 在十进制下的数码和. 因为 对所有 成立,而 (因为 ),所以 . 因此 是集合 中的一个数. 的末位为 1 (因为 ),所以 . 如果 ,则 . 记 分别为 的奇数位、偶数位上的数码和,则 . 另一方面, 被 1980 整除,因此也被 11 整除. 根据例 1.13 (b), 是 11 的倍数,因此 . 但是 ,矛盾. 所以对所有的 .
例 1.15. 设 是第 个费马数,证明: 对所有 成立.
证: 只需证明 . 注意
根据定理 1.9,若 ,则 . 因此只需证明 ,等价地, ,这是显然的.
定理 1.9 的直接推论也很有用:
命题 1.16. 若 是整系数多项式,则对所有整数 有
因此,若 对某整数 成立,则 .
证: 记
其中 是整数, . 则
根据定理 1.9,每个求和项都是 的倍数,因此 也是 的倍数.
例 1.17. 设 是整系数多项式, 是正整数,满足 . 证明: 存在无穷多个正整数 ,满足 .
证: 取 是正整数. 则 ,是 的倍数. 因此 . 由 的任意性,结论是显然的.
1.1.2 整除和大小
本节我们想要强调的另一个整除性质是它和整数集序关系的联系. 下面一个命题粗糙地说明了一个整数的因子不能超过这个数. 注意到 1 是 -2 的因子, 但是 1 比 -2 大, 因此我们在严格叙述这个命题时需要注意这一点, 最终这个命题可如下描述:
命题 1.18. 若 整除 ,且 ,则 .
证: 记 ,则 (因为 ),因此 .
注释 1.19. 条件 在命题 1.18 中很关键,0 在此是一个很特殊的数: 它是唯一一个有无穷多个因子的数. 0 可以被所有整数整除,因为对每个整数 ,都可以写出 . 另一方面,若 有无穷多个因子,则必有 ; 否则根据前面的命题, 的所有因子 都满足 ,这样 就只有有限个因子. 下面的例子是上面观点的应用.
例 1.20. (俄罗斯1964) 设 是整数, 是正整数且满足 对无穷多个整数 成立,证明: .
证: 对任何整数 ,现在有 . 根据题目条件又有 ,于是
由 的任意性, 有无穷多个因子,因此 ,证毕.
前面命题的一个推论是下面的性质:
推论 1.21. 若 是整数,满足 ,则 ,即 .
证: 当 或 时结论是显然的. 另一方面,前面的命题给出 及 ,因此 .
例 1.22. 求所有整数 ,满足对所有的相异整数 ,有 .
证: 恒等式
说明 对所有 成立. 取 ,其中 是一个正整数,可得 ,因此 . 由 的任意性, 有无穷多个因子,因此 . 反之,由完全平方公式, 确实是问题的一个解.
例 1.23. (普特南2007) 设 是一个系数为正整数的非常数多项式. 证明: 若 是一个正整数,则 整除 当且仅当 .
证: 首先有 . 若 ,这说明 被 整除. 另一方面,当 时,因为 非常数并且系数为正, . 因此 不能被 整除.
例 1.24. (a) 证明: 对任何正整数 ,存在不同的正整数 和 ,满足对每个 被 整除.
(b) 假设 是正整数,满足 整除 对每个正整数 成立. 证明: 证: (a) 我们有 当且仅当 . 因此只要 是 的倍数即可,例如取 .
(b) 像 (a) 中一样推导,可以看出 必须是 的倍数,且对所有正整数 成立. 注释 1.19 说明 ,证毕.
例 1.25. 设 是整系数多项式,次数 . 属于序列 的连续整数个数的最大值是多少
证: 对于多项式 ,有 ,因此可以有 个连续整数在序列 中. 下证不会有更多的连续整数.
用反证法,假设能找到 以及整数 ,满足 . 则 是 的倍数. 因此 对所有 成立.
显然是两两不同的一组数 (它们在 下的像两两不同),因此在序列 不会有变号(如果存在某个 使得 与 . 因此序列 或者全为 1,或者全为 -1 . 我们可以找到符号 ,满足 .
于是 对 成立. 也就是多项式 有至少 个不同的根 ,这与 是 次多项式矛盾.
因此所求最大值为 .
例 1.26. 设 是整系数多项式,次数 . 证明: 方程 最多有 个整数解.
证: 设 是两个不同的整数,满足 和 . 则 是 的倍数,而前者反过来又是 . 因此必然有
现在考虑整数 满足 对 成立. 前面表明 对 成立. 我们将证明 是单调的序列. 实际上
因此 和 有相同的符号,说明序列是单调的.
不妨设 是递增序列 (另一种情形类似),则必有 对所有 成立. 因此存在常数 ,满足 . 因为 的次数是 ,它最多有 个不同根,因此 .
注释 1.27. 一个推广的题目 (其中 替换成 ) 在 IMO 2006中出现过.
例 1.28. 设 是递增的正整数无穷数列,满足 整除 对所有 成立. 证明:存在正整数 ,满足
对所有 成立.
证: 根据假设,存在正整数序列 ,满足对所有 ,有
将对应指标 的上述关系式与指标 的关系式相减,得到
因此,由 ,有
于是 ,对所有 成立.
因为不存在严格递减的正整数无穷序列,所以存在 ,当 时,有 . 设 ,则 . 关系式 (1) 变为 .
特别地, 是 的倍数. 记 ,可得 ,于是 对 成立,即 对 成立. 直接归纳可得 对所有 和 成立. 特别地, 对所有 成立. 必有 ,于是
对所有 成立.
从整除性和序关系的联系以及奇偶性很容易得到下面的定理:
定理 1.29. 设 是非零整数,则存在唯一的整数对(a, b)满足 是奇数, 使得 .
证: 先证明唯一性. 假设 ,其中 是奇数. 若 ,不妨设 ,则 是偶数,矛盾. 因此 ,于是 .
下证存在性. 考虑整除 的 2 的幂的集合,此集合是有限集: 若 整除 , 则 . 因此存在一个最大的整数 ,使 . 记 是整数. 如果 是偶数,则 是整数,进而 ,与 的最大性矛盾. 因此 是奇数, 存在性得证.
注释 1.30. (a) 从定理 1.29 容易得到,若 是整数,满足 是 2 的幂,即 , 是整数,则 和 ( 和 本身不一定是,可能有符号)也都是 2 的幂.
(b) 从题目的唯一性证明部分可得,若 是偶数, 是 的一个奇数因子,则 整除 . 这是我们的第一个在同余式中使用消去律的例子,后面会经常用到.
还有一个实际中也常用的例子如下:
定理 1.31. 若 是奇数,则对所有 ,有
证: 看因式分解式
因为 是奇数, 是 8 的倍数,而 每一个都是偶数,因此 是 的倍数,证毕.
这个结论也可以对 用归纳法证明: 当 时相当于 ,这已经证明过. 假设已有 ,则
证毕.
前面两个定理在整本书中都经常用到, 下面几个例子说明了如何使用它们.
例 1.32. 设 是大于 1 的整数,证明: 是奇数当且仅当 整除 . 证: 若 是奇数,则 是 的倍数,其中 . 因此 进而 是 的倍数.
若 是偶数,记 是奇数. 若 是奇数,则 ; 若 是偶数,则 . 因此
所以 不能整除 .
例 1.33. 证明: 若 ,则 不是整数.
证: 设 是所有不超过 的奇数的乘积, 是满足 的最大整数. 下证 不是整数.
若 且 ,则 可以写成 的形式,其中 , 是奇数. 因此 是整数.
于是 是某整数. 但是 是奇数, 不是整数,于是 ,进而 不是整数.
例 1.34. 是否存在二元整系数多项式 ,满足下列条件:
(a) 方程 没有整数解.
(b) 对每个正整数 ,存在整数 满足 .
证: 下证 满足要求. 显然 没有整数解, 因为它的解必须满足 或 . 现在设 是任意正整数,记 , 是奇数. 注意到 (因为 ),可以记 是某整数. 又记 ( 是整数,因为 是奇数),则有
是 的倍数.
例 1.35. (土耳其TST2016) 设 表示正整数集,求所有的函数 满足对所有的 有 和 成立.
证: 显然对任何正奇数 给出题目的一个解. 我们证明这些是所有的解.
首先,看到 ,因为 ,并且 是正整数. 接下来,考虑 ,记 ,其中整数 . 假设 ,则
因此 ,矛盾. 所以 . 因为 对所有 成立,所以 对所有 成立. 而 ,因此 是奇数.
最后,对任何 和 ,有 . 由于 是奇数,有 ,因此 . 固定 ,由 的任意性可得 对所有 成立. (因为 有无穷多个因子,就是 形式的所有数,其中 .)
我们接下来看一些更难的例子, 这些例子大多数使用了前面出现的所有技巧. 第一个例子是一个著名的 IMO 题目, 现在已经是经典题目. 其证明方法 (称为无穷递降法)可以追溯到费马, 关键用到了整数的有序性. 在很多情况下, 无穷递降法可以用于证明某个丢番图方程 没有解或者仅有 “平凡解” (指一眼可以看出的那些解). 其思想是, 从方程的一个可能解或者非平凡解, 导出一个 “更小的” 解. 如果这个 “更小” 解依旧是非平凡的, 可以继续这个步骤. 这样会得到一系列越来越小的解, 必然会终止. 也可以用反证法, 直接考虑一个 “极小” 解, 然后得到一个 “更小” 解导致矛盾.
在研究更难的问题前, 先通过一个简单例子来看这种方法是如何成功的. 考虑方程
我们将证明此方程只有平凡解,即 . 假设有一个非平凡解(x, y, z), 则 3 整除 ,通过枚举很容易说明 必然都是 3 的倍数. 记 ,方程变为 ,进而 是 3 的倍数 (否则 ,矛盾),记 ,方程又变为 ,和原方程形式完全相同. 因此 也是方程的一个解,因为(x, y, z)非平凡, 也非平凡. 但是
所以解 比解(x, y, z)“更小”,这里的意思是解的绝对值之和更小. 如果开始考虑的非平凡解要求是使 最小的解,马上得到矛盾.
例 1.36. 设 是正整数,满足 整除 ,证明: 是完全平方数.
证: 假设对某 ,上面的命题不成立,找一组这样的(a, b)并使 达到最小可能值. 设 ,根据假设 不是完全平方数. 由于方程关于 和 对称,不妨设 . 二次方程
有一个整数解 . 根据韦达定理, 是方程的另一个解. 也是一个整数,并且因为 不是完全平方数,所以 非零.
我们下证 是正整数. 否则 ,则 ,于是 . 接下来
矛盾. 这样 是问题的另一组正整数解. 这时的商 不变,依旧不是平方数. 根据(a, b)的最小性,必有 ,即 . 这也不可能, 因为利用 ,有
所以实际上,不会有满足题目中的整除关系但 不是完全平方数的反例存在,证毕.
例 1.37.设 是正整数,满足 ,证明: .
证: 因为 ,所以 . 又由题目条件, ,因此 .
我们像例 1.36 中一样讨论,设(a, b)是满足 ,并且使 最小的一组解. 不妨设 ,记 ,然后考虑方程
的另一个解
显然 也是正整数,而且 满足 , 这样 是另一组满足不等条件的解.
根据(a, b)的最小性得到 ,所以 . 然而由 可以得出 ,这样 . 因为 , 可得 ,矛盾.
因此所假设的满足 的方程的解(a, b)不存在,证毕.
注释 1.38. 下面是一些类似的题目,都可以用同样的解题过程处理:
(a) 设正整数 满足 . 证明: .
(b) 设正整数 满足 被 整除. 证明: .
(c) (AMM11374) 设 是正整数,满足
证明: .
(d) (USATST2002) 求所有的有序正整数对(m, n),满足 整除 .
(e)(USATST2009)求所有的正整数对(m, n),满足 整除 .
(f) (Hurwitz) 证明: 当 时,方程
没有正整数解.
例 1.39. 设 和 是大于 1 的整数,满足 和 . 证明: 或者
证: 记 是正整数. 则 ,所以 . 但
所以 . 特别有 ,进一步写成 ,因此 .
接下来, ,且
因为 ,因此 .
现在讨论三种情形. 若 ,则 ,属于题目所给结论的情况之一. 若 ,则由上一段得到 ,显然矛盾. 最后, 若 ,则由上一段得到 ,所以 . 结合第一段可得 ,然后 ,也属于题目所给结论的情况之一, 证毕.
第一章 整除
第一章比较初等, 讨论了整除的性质、同余和带余除法. 这些概念后续经常用到, 代表了算术的基础, 更深入的内容后续在此之上建立. 我们会更多地使用非标准的例子或应用, 其中一些是非平凡的 (例如有限差分和同余方面的应用).
本书中的变量,如没有明显指出,可以默认是正整数,总是用 表示正整数的集合.
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 已足够使用；在某些情形下,需要对 进行更细致的分析.
下面的结果是定理 1.9 用同余式语言的描述.
推论 1.11. 设 是整数, 是正整数, 是 的正因子:
(a) 若 ,则 .
(b) 若 ,则 .
(c) 若 ,且 是奇数,则 .
例 1.12. 利用 ,证明: .
证: 首先有 ,所以 . 而 , 所以 . 因此 . 正是我们需要的.
例 1.13. (a) 证明: 正整数 和它在十进制下数码和的差被 9 整除.
(b) 设 是正整数, 分别是 在十进制下奇数位和偶数位上的数码和 ( 的最后一位为第 0 位). 证明: .
证: (a) 记
其中 是十进制下的数码, . 则
是 9 的倍数, 因为根据定理 1.9, 每一个 10 的幂减 1 是 9 的倍数.
(b) 证明和(a)相同,关键是 对所有 成立.
例 1.14. (Kvant 676) 证明: 对所有的正整数 的数码和不小于 19.
证: 用 表示 在十进制下的数码和. 因为 对所有 成立,而 (因为 ),所以 . 因此 是集合 中的一个数. 的末位为 1 (因为 ),所以 . 如果 ,则 . 记 分别为 的奇数位、偶数位上的数码和,则 . 另一方面, 被 1980 整除,因此也被 11 整除. 根据例 1.13 (b), 是 11 的倍数,因此 . 但是 ,矛盾. 所以对所有的 .
例 1.15. 设 是第 个费马数,证明: 对所有 成立.
证: 只需证明 . 注意
根据定理 1.9,若 ,则 . 因此只需证明 ,等价地, ,这是显然的.
定理 1.9 的直接推论也很有用:
命题 1.16. 若 是整系数多项式,则对所有整数 有
因此,若 对某整数 成立,则 .
证: 记
其中 是整数, . 则
根据定理 1.9,每个求和项都是 的倍数,因此 也是 的倍数.
例 1.17. 设 是整系数多项式, 是正整数,满足 . 证明: 存在无穷多个正整数 ,满足 .
证: 取 是正整数. 则 ,是 的倍数. 因此 . 由 的任意性,结论是显然的.
1.1.2 整除和大小
本节我们想要强调的另一个整除性质是它和整数集序关系的联系. 下面一个命题粗糙地说明了一个整数的因子不能超过这个数. 注意到 1 是 -2 的因子, 但是 1 比 -2 大, 因此我们在严格叙述这个命题时需要注意这一点, 最终这个命题可如下描述:
命题 1.18. 若 整除 ,且 ,则 .
证: 记 ,则 (因为 ),因此 .
注释 1.19. 条件 在命题 1.18 中很关键,0 在此是一个很特殊的数: 它是唯一一个有无穷多个因子的数. 0 可以被所有整数整除,因为对每个整数 ,都可以写出 . 另一方面,若 有无穷多个因子,则必有 ; 否则根据前面的命题, 的所有因子 都满足 ,这样 就只有有限个因子. 下面的例子是上面观点的应用.
例 1.20. (俄罗斯1964) 设 是整数, 是正整数且满足 对无穷多个整数 成立,证明: .
证: 对任何整数 ,现在有 . 根据题目条件又有 ,于是
由 的任意性, 有无穷多个因子,因此 ,证毕.
前面命题的一个推论是下面的性质:
推论 1.21. 若 是整数,满足 ,则 ,即 .
证: 当 或 时结论是显然的. 另一方面,前面的命题给出 及 ,因此 .
例 1.22. 求所有整数 ,满足对所有的相异整数 ,有 .
证: 恒等式
说明 对所有 成立. 取 ,其中 是一个正整数,可得 ,因此 . 由 的任意性, 有无穷多个因子,因此 . 反之,由完全平方公式, 确实是问题的一个解.
例 1.23. (普特南2007) 设 是一个系数为正整数的非常数多项式. 证明: 若 是一个正整数,则 整除 当且仅当 .
证: 首先有 . 若 ,这说明 被 整除. 另一方面,当 时,因为 非常数并且系数为正, . 因此 不能被 整除.
例 1.24. (a) 证明: 对任何正整数 ,存在不同的正整数 和 ,满足对每个 被 整除.
(b) 假设 是正整数,满足 整除 对每个正整数 成立. 证明: 证: (a) 我们有 当且仅当 . 因此只要 是 的倍数即可,例如取 .
(b) 像 (a) 中一样推导,可以看出 必须是 的倍数,且对所有正整数 成立. 注释 1.19 说明 ,证毕.
例 1.25. 设 是整系数多项式,次数 . 属于序列 的连续整数个数的最大值是多少
证: 对于多项式 ,有 ,因此可以有 个连续整数在序列 中. 下证不会有更多的连续整数.
用反证法,假设能找到 以及整数 ,满足 . 则 是 的倍数. 因此 对所有 成立.
显然是两两不同的一组数 (它们在 下的像两两不同),因此在序列 不会有变号(如果存在某个 使得 与 . 因此序列 或者全为 1,或者全为 -1 . 我们可以找到符号 ,满足 .
于是 对 成立. 也就是多项式 有至少 个不同的根 ,这与 是 次多项式矛盾.
因此所求最大值为 .
例 1.26. 设 是整系数多项式,次数 . 证明: 方程 最多有 个整数解.
证: 设 是两个不同的整数,满足 和 . 则 是 的倍数,而前者反过来又是 . 因此必然有
现在考虑整数 满足 对 成立. 前面表明 对 成立. 我们将证明 是单调的序列. 实际上
因此 和 有相同的符号,说明序列是单调的.
不妨设 是递增序列 (另一种情形类似),则必有 对所有 成立. 因此存在常数 ,满足 . 因为 的次数是 ,它最多有 个不同根,因此 .
注释 1.27. 一个推广的题目 (其中 替换成 ) 在 IMO 2006中出现过.
例 1.28. 设 是递增的正整数无穷数列,满足 整除 对所有 成立. 证明:存在正整数 ,满足
对所有 成立.
证: 根据假设,存在正整数序列 ,满足对所有 ,有
将对应指标 的上述关系式与指标 的关系式相减,得到
因此,由 ,有
于是 ,对所有 成立.
因为不存在严格递减的正整数无穷序列,所以存在 ,当 时,有 . 设 ,则 . 关系式 (1) 变为 .
特别地, 是 的倍数. 记 ,可得 ,于是 对 成立,即 对 成立. 直接归纳可得 对所有 和 成立. 特别地, 对所有 成立. 必有 ,于是
对所有 成立.
从整除性和序关系的联系以及奇偶性很容易得到下面的定理:
定理 1.29. 设 是非零整数,则存在唯一的整数对(a, b)满足 是奇数, 使得 .
证: 先证明唯一性. 假设 ,其中 是奇数. 若 ,不妨设 ,则 是偶数,矛盾. 因此 ,于是 .
下证存在性. 考虑整除 的 2 的幂的集合,此集合是有限集: 若 整除 , 则 . 因此存在一个最大的整数 ,使 . 记 是整数. 如果 是偶数,则 是整数,进而 ,与 的最大性矛盾. 因此 是奇数, 存在性得证.
注释 1.30. (a) 从定理 1.29 容易得到,若 是整数,满足 是 2 的幂,即 , 是整数,则 和 ( 和 本身不一定是,可能有符号)也都是 2 的幂.
(b) 从题目的唯一性证明部分可得,若 是偶数, 是 的一个奇数因子,则 整除 . 这是我们的第一个在同余式中使用消去律的例子,后面会经常用到.
还有一个实际中也常用的例子如下:
定理 1.31. 若 是奇数,则对所有 ,有
证: 看因式分解式
因为 是奇数, 是 8 的倍数,而 每一个都是偶数,因此 是 的倍数,证毕.
这个结论也可以对 用归纳法证明: 当 时相当于 ,这已经证明过. 假设已有 ,则
证毕.
前面两个定理在整本书中都经常用到, 下面几个例子说明了如何使用它们.
例 1.32. 设 是大于 1 的整数,证明: 是奇数当且仅当 整除 . 证: 若 是奇数,则 是 的倍数,其中 . 因此 进而 是 的倍数.
若 是偶数,记 是奇数. 若 是奇数,则 ; 若 是偶数,则 . 因此
所以 不能整除 .
例 1.33. 证明: 若 ,则 不是整数.
证: 设 是所有不超过 的奇数的乘积, 是满足 的最大整数. 下证 不是整数.
若 且 ,则 可以写成 的形式,其中 , 是奇数. 因此 是整数.
于是 是某整数. 但是 是奇数, 不是整数,于是 ,进而 不是整数.
例 1.34. 是否存在二元整系数多项式 ,满足下列条件:
(a) 方程 没有整数解.
(b) 对每个正整数 ,存在整数 满足 .
证: 下证 满足要求. 显然 没有整数解, 因为它的解必须满足 或 . 现在设 是任意正整数,记 , 是奇数. 注意到 (因为 ),可以记 是某整数. 又记 ( 是整数,因为 是奇数),则有
是 的倍数.
例 1.35. (土耳其TST2016) 设 表示正整数集,求所有的函数 满足对所有的 有 和 成立.
证: 显然对任何正奇数 给出题目的一个解. 我们证明这些是所有的解.
首先,看到 ,因为 ,并且 是正整数. 接下来,考虑 ,记 ,其中整数 . 假设 ,则
因此 ,矛盾. 所以 . 因为 对所有 成立,所以 对所有 成立. 而 ,因此 是奇数.
最后,对任何 和 ,有 . 由于 是奇数,有 ,因此 . 固定 ,由 的任意性可得 对所有 成立. (因为 有无穷多个因子,就是 形式的所有数,其中 .)
我们接下来看一些更难的例子, 这些例子大多数使用了前面出现的所有技巧. 第一个例子是一个著名的 IMO 题目, 现在已经是经典题目. 其证明方法 (称为无穷递降法)可以追溯到费马, 关键用到了整数的有序性. 在很多情况下, 无穷递降法可以用于证明某个丢番图方程 没有解或者仅有 “平凡解” (指一眼可以看出的那些解). 其思想是, 从方程的一个可能解或者非平凡解, 导出一个 “更小的” 解. 如果这个 “更小” 解依旧是非平凡的, 可以继续这个步骤. 这样会得到一系列越来越小的解, 必然会终止. 也可以用反证法, 直接考虑一个 “极小” 解, 然后得到一个 “更小” 解导致矛盾.
在研究更难的问题前, 先通过一个简单例子来看这种方法是如何成功的. 考虑方程
我们将证明此方程只有平凡解,即 . 假设有一个非平凡解(x, y, z), 则 3 整除 ,通过枚举很容易说明 必然都是 3 的倍数. 记 ,方程变为 ,进而 是 3 的倍数 (否则 ,矛盾),记 ,方程又变为 ,和原方程形式完全相同. 因此 也是方程的一个解,因为(x, y, z)非平凡, 也非平凡. 但是
所以解 比解(x, y, z)“更小”,这里的意思是解的绝对值之和更小. 如果开始考虑的非平凡解要求是使 最小的解,马上得到矛盾.
例 1.36. 设 是正整数,满足 整除 ,证明: 是完全平方数.
证: 假设对某 ,上面的命题不成立,找一组这样的(a, b)并使 达到最小可能值. 设 ,根据假设 不是完全平方数. 由于方程关于 和 对称,不妨设 . 二次方程
有一个整数解 . 根据韦达定理, 是方程的另一个解. 也是一个整数,并且因为 不是完全平方数,所以 非零.
我们下证 是正整数. 否则 ,则 ,于是 . 接下来
矛盾. 这样 是问题的另一组正整数解. 这时的商 不变,依旧不是平方数. 根据(a, b)的最小性,必有 ,即 . 这也不可能, 因为利用 ,有
所以实际上,不会有满足题目中的整除关系但 不是完全平方数的反例存在,证毕.
例 1.37.设 是正整数,满足 ,证明: .
证: 因为 ,所以 . 又由题目条件, ,因此 .
我们像例 1.36 中一样讨论,设(a, b)是满足 ,并且使 最小的一组解. 不妨设 ,记 ,然后考虑方程
的另一个解
显然 也是正整数,而且 满足 , 这样 是另一组满足不等条件的解.
根据(a, b)的最小性得到 ,所以 . 然而由 可以得出 ,这样 . 因为 , 可得 ,矛盾.
因此所假设的满足 的方程的解(a, b)不存在,证毕.
注释 1.38. 下面是一些类似的题目,都可以用同样的解题过程处理:
(a) 设正整数 满足 . 证明: .
(b) 设正整数 满足 被 整除. 证明: .
(c) (AMM11374) 设 是正整数,满足
证明: .
(d) (USATST2002) 求所有的有序正整数对(m, n),满足 整除 .
(e)(USATST2009)求所有的正整数对(m, n),满足 整除 .
(f) (Hurwitz) 证明: 当 时,方程
没有正整数解.
例 1.39. 设 和 是大于 1 的整数,满足 和 . 证明: 或者
证: 记 是正整数. 则 ,所以 . 但
所以 . 特别有 ,进一步写成 ,因此 .
接下来, ,且
因为 ,因此 .
现在讨论三种情形. 若 ,则 ,属于题目所给结论的情况之一. 若 ,则由上一段得到 ,显然矛盾. 最后, 若 ,则由上一段得到 ,所以 . 结合第一段可得 ,然后 ,也属于题目所给结论的情况之一, 证毕.
同课章节目录