第1讲〓整除 本讲概述 我们知道，整数集Z对于加减乘运算是封闭的，即两个整数的和、差、积仍为整数，而商是否为整数并不一定，因此我们格外关注这一不平凡的情形，这就是数论中最基本的概念与关系——整除. 本讲的重点为掌握并活用整除的数论与代数性质，例题与习题丰富多彩，本讲相当多问题背后有更深层次的关联，将在后续章节徐徐展开. ［知识拓展］ 一、 整除的定义 对于整数a,b(b≠0)，若存在整数c，使得a=bc，则称b整除a，同时称b是a的约数(因数)，a是b的倍数，记作b|a.一个整数b不能整除另一个整数a，是指对任一整数c，都有a≠bc，记作ba. 评注 要求b≠0，正如除法中要求除数不为0.但是，a可以为0，且由定义可知，任何非零整数都整除0.零在数论中有着独特而重要的地位. 二、 整除的重要性质 (1) 传递性 若b|a，且a|c，则b|c. 评注 学习新知识，应注重类比,以此来加深体会.我们学过的许多关系都具有传递性，例如： 数量关系中的等于、大于、小于； 直线位置关系中的平行； 集合中的包含，即BA，且AC，则BC. 反之，也有许多关系不具有传递性，例如： 数量关系中的不相等； 位置关系中的垂直.我们甚至可以联系生活实际，“敌对关系”“父子关系”也不具有传递性——敌人的敌人或许是朋友，而父亲的父亲是爷爷. (2) 封闭性 整数b的倍数构成的集合{x|x∈Z，b∈Z，b|x}对加减乘法封闭，即若b|a，且b|c，则b|a±c且b|ac(可强化为b2|ac).进一步，对任意整数m,n，有b|ma+nc，我们还可以在右侧加上b的倍数，整除关系依然成立，即对任意整数t，有b|ma+nc+tb. 评注 整数集对于除法不封闭，有理数应运而生.有理数集对于四则运算均封闭，似乎完美，难怪毕达哥拉斯误以为万物皆有理数，直到2的发现. 整数集对于加、减、乘运算封闭的重要性在于，我们可以选择合适的系数(例如m,n,t等)，利用加、减、乘运算来简化整除式的右边.值得强调的是，b|a且b|c是b|ma+nc的充分不必要条件，这种不等价正是数论问题如此困难的原因之一. (3) 数量关系 若b|a，则a=0或|a|≥|b|. 证明： 由b|a，可知存在整数c，使得a=bc. 若c=0，则a=0； 若c≠0，则|c|≥1(整数的离散性)，所以|a|=|bc|=|b||c|≥|b|. 由此我们得到一个重要的推论，若b|a且a|b，则|a|=|b|. 评注 数论与代数联系紧密.整除可以带给我们解代数题新的思路，例如欲证两个正整数a与b相等，只需证明b|a且a|b.这与下述两种思路如出一辙，欲证两个实数a与b相等，只需证明b≥a且a≥b； 欲证集合A=B，只需证明AB且BA. 三、 因式分解 整除关系有时会关联代数式的因式分解，我们介绍常见的几种. (1) 若n是正整数，则 xn-yn=(x-y)(xn-1+xn-2y+xn-3y2+…+xyn-2+yn-1)； (2) 若n是正奇数，则在上式中用-y替换y可得 xn+yn=(x+y)(xn-1-xn-2y+xn-3y2-…-xyn-2+yn-1)； (3) x4+4y4=(x2+2y2)2-4x2y2=(x2+2y2+2xy)(x2+2y2-2xy)； (4) a3+b3+c3-3abc=(a+b+c)(a2+b2+c2-ab-ac-bc) =12(a+b+c)［(a-b)2+(b-c)2+(c-a)2］； (5) 利用(1)可推出： 若f(x)为整系数多项式，则对于互异的整数m,n,有m-n|f(m)-f(n). 评注 限于篇幅，本书没有专门设置章节讲解多项式理论，而会直接使用一些常见的结果，或是将部分重要的结论在各讲的知识拓展与例题或习题中作证明、引用和补充，因此希望读者朋友自主掌握一定的多项式知识.拥有扎实的代数基本功是学好数论的前提. 四、 带余除法 对于a,b∈Z，b>0，存在唯一一组整数对(q,r)，0≤r|a-bn|，又b-k|a-bn，所以a-bn=0. 例4(2004捷克和斯洛伐克数学奥林匹克)求正整数n，使得 ∑nk=1nk! 是一个整数. 点拨 本题通分后，欲使n!整除分子，我们考虑必要条件n-1整除分子，从而化简该式. 【解析】通分， n1!+n2!+…+nn! =n×n×(n-1)×…×2+n×n×(n-1)×…×3+…+n×n+nn!. 记Sn=n×n×(n-1)×…×2+n×n×(n-1)×…×3+…+n×n+n. 当n=1时，题干中的式子等于1，是整数； 当n≥2时，原式的值是一个整数n!|Sn，这要求n-1|Sn，注意到Sn的表达式中的前n-2个加项均为n-1的倍数，所以n-1|Snn-1|n×n+n×1. 利用代数变形，我们有 n-1|n×n+n×1=n2+n=(n+2)(n-1)+2, 所以n-1|2，则n∈{2,3}，检验知均满足题意. 综上所述，所求的正整数n=1,2,3. 例5(2023波兰数学奥林匹克)设a1,a2,a3,…是正整数数列，满足对任意正整数k,l，均有k+l|ak+al.求证： 对任意正整数k>l，均有k-l|ak-al. 点拨 我们希望能够将减法变为加法，结合整除的传递性，找到一个正整数m，满足k-l|k+m，k-l|l+m，这很容易. 【解析】对正整数k>l，易知存在正整数n，使得(n-1)k>nl，例如n=2kl. 对这样的n，令m=(n-1)k-nl，则k-l|k+m,k-l|l+m. 由条件可知k+m|ak+am,l+m|al+am，所以k-l|ak+am,k-l|al+am，所以 k-l|(ak+am)-(al+am)=ak-al. 例6(2023俄罗斯数学奥林匹克)求最大的正整数n，使得n,n+1,n+2,…,n+20的乘积能被它们之中一个的平方整除. 点拨 写出整除关系式，利用整除的性质，将关系式右侧变形处理为常数. 【解析】设i∈{0,1,2,…,20}，使得 (n+i)2|n(n+1)(n+2)…(n+20), 则 n+i∏0≤j≤20j≠i(n+j). 所以 n+i∏0≤j≤20j≠i(n+j-(n+i))=∏0≤j≤20j≠i(j-i), 又 ∏0≤j≤20j≠i(j-i)=i!(n-i)!=20!Ci20≤20!, 所以n≤n+i≤20!，又当n=20!时， n(n+1)(n+2)…(n+20)n2=C2020+n∈Z, 综上所述，n的最大值为20!. 评注 当f(x)为整系数多项式时，恒有n+i|f(x)-f(x-(n+i))，所以若n+i|f(n)，则n+i|f(n-(n+i))=f(-i)，这正是本题的关键一步.当然，学习了同余的相关知识之后，我们将有新的理解. 例7M={1,2,…,2025}，AM，且对于A中的任意两个不同元素a,b，a-ba+b，求|A|的最大值. 【解析】|A|的最大值为675. 一方面，取A={1,4,7,10,…,2023}，则对于A中的任意两个不同元素a,b，有3|a-b，但3a+b，所以a-ba+b，所以这样的A满足要求，此时|A|=675. 另一方面，考虑如下的675个M的三元子集，Sk={3k-2,3k-1,3k}，k=1,2,…,675，显然S1,S2,…,S675构成了M的一个划分(两两不交且并集为M)，又注意到每个Sk中的任两个元素之差整除这两个元素之和，所以A至多含有每个Sk中的一个元素，因此|A|≤675. 综上所述，|A|的最大值为675. 评注 组合最值问题是竞赛的热点与难点，这类问题求解一般分为两部分，证明目标值的不等式和构造取等情形.这是一道数论中的组合最值问题，解题关键是注意到连续的三个数中最多取一个(a-ba+ba-b2aa-b2)，从而构造抽屉来作局部估计(也可利用相邻的取数至少相差3作间距估计)，得到|A|的不等式； 构造则又是典型的不等价思维，要使a-ba+b，只需a-b有“独特”的素因子即可.习题12与本题和而不同，供读者练习. B组 例8(1966普特南数学竞赛)给定mn+1个正整数a1,a2,…,amn+1，且0