数学竞赛中的数论问题.doc

《数学竞赛中的数论问题.doc》由会员分享，可在线阅读，更多相关《数学竞赛中的数论问题.doc（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流数学竞赛中的数论问题.精品文档.数学竞赛中的数论问题 罗增儒引言数论的认识：数论是关于数的学问，主要研究整数，重点对象是正整数，对中学生可以说，数论是研究正整数的一个数学分支什么是正整数呢？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描述，正整数1，2，3，是这样一个集合：（1）有一个最小的数1 （2）每一个数的后面都有且只有一个后继数；除1之外，每一个数的都是且只是一个数的后继数这个结构很像数学归纳法，事实上，有这样的归纳公理：（3）对的子集，若，且当时，有后继数，则就是这么一个简单的数集，里面却有无穷无尽的奥秘，有

2、的奥秘甚至使得人们怀疑：人类的智慧还没有成熟到解决它的程度比如，哥德巴赫猜想：1742年6月7日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数，由4开始，都可以表示为两个素数和的形式，任何奇数，由7开始，都可以表示为三个素数的和后者是前者的推论，也可独立证明（已解决）“表示为两个素数和的形式”就是著名的哥德巴赫猜想，简称1+1欧拉认为这是对的，但证不出来1900年希尔伯特将其归入23个问题中的第8个问题1966年陈景润证得：一个素数+素数素数（1+2），至今仍无人超越陈景润的数学教师沈元很重视利用名人、名言、名事去激励学生，他曾多次在开讲时，说过这样的话:“自然科学的皇后是数学，

3、数学的皇冠是数论，哥德巴赫猜想则是皇冠上的明珠”陈景润就是由此而受到了启示和激励，展开了艰苦卓绝的终生奋斗和灿烂辉煌的奋斗终生，离摘取“皇冠上的明珠”仅一步之遥数论题涉及的知识不是很多，但用不多的知识来解决问题往往就需要较强的能力和精明多的技巧，有人说：用以发现数学人才，在初等数学中再也没有比数论教材更好的课程了任何学生如能把当今一本数论教材中的练习做出，就应当受到鼓励，劝他（她）将来去从事数学方面的工作（UDudley数论基础前言）下面，是一个有趣的故事当代最高产的数学家厄尔多斯听说一个叫波萨（匈牙利，1948）的小男孩很聪明，就问了他一个问题加以考察（1959）：如果你手头上有个正整数，这

4、些正整数小于或等于，那么你一定有一对整数是互素的，你知道这是什么原因吗？不到12岁的波萨只用了1分半钟，就给出了问题的解答他将1分成（1，2），（3，4），（）共个抽屉，手头的个正整数一定有两个属于同一抽屉，这两个数是相邻的正整数，必定互素通过这个问题，厄尔多斯认定波萨是个难得的英才，就精心加以培养，不到两年，14岁的波萨就发表了图论中“波萨定理”重视数学能力的数学竞赛，已经广泛采用数论题目，是数学竞赛四大支柱之一，四大支柱是：代数，几何，初等数论，组合初步（俗称代数题、几何题、算术题和智力题）高中竞赛加试四道题正好是四大模块各一题，分别是几何题、代数题、数论题、组合题，一试中也会有数论题数论

5、受到数学竞赛的青睐可能还有一个技术上的原因，就是它能方便地提供从小学到大学各个层面的、新鲜而有趣的题目数论题的主要类型：在初中竞赛大纲中，数论的内容列有：十进制整数及表示方法；整除性，被2、3、4、5、8、9、11等数整除的判定；素数和合数，最大公约数与最小公倍数；奇数和偶数，奇偶性分析；带余除法和利用余数分类；完全平方数；因数分解的表示法，约数个数的计算； 简单的一次不定方程 在高中竞赛大纲中，数论的内容列有：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数，费马小定理，格点及其性质，无穷递降法，欧拉定理，孙子定理根据已出现的试题统计，中学数学竞赛中的数论问题的

6、主要有8个重点类型：（1）奇数与偶数（奇偶分析法、01法）；（2）约数与倍数、素数与合数；（3）平方数；（4）整除；（5）同余；（6）不定方程；（7）数论函数、高斯函数、欧拉函数；（8）进位制（十进制、二进制）下面，我们首先介绍数论题的基本内容（10个定义、18条定理），然后，对数学竞赛中的数论问题作分类讲解第一讲 数论题的基本内容中学数学竞赛中的数论问题涉及的数论内容主要有10个定义、18条定理首先约定，本文中的字母均表示整数定义1 （带余除法）给定整数如果有整数满足则和分别称为除以的商和余数特别的，时，则称被整除，记作，或者说是的倍数，而是的约数（的存在性由定理1证明）定义2 （最大公约数

7、）设整数中至少有一个不等于零，这个数的最大公约数是能整除其中每一个整数的最大正整数，记作 中的没有顺序，最大公约数也称最大公因数简单性质：一个功能：可以把对整数的研究转化为对非负整数的研究定义3 （最小公倍数）非零整数的最小公倍数是能被其中每一个所整除的最小正整数，记作简单性质：如果是正整数的公倍数，则存在正整数使证明若不然，有（），由都是的公倍数得也是的公倍数，但，与的最小性矛盾故定义4 如果整数 满足，则称与是互素的（也称互质）定义5 大于1且除1及其自身外没有别的正整数因子的正整数，称为素数（也称质数）其余大于1的正整数称为合数；数1既不是素数也不是合数定理1 若是两个整数，则存在两个实

8、数，使，并且是唯一性证明1 先证存在性作序列则必在上述序列的某两项之间，从而存在一个整数，使即 ，取 ， ，得 ，即存在两个实数，使 再证唯一性假设不唯一，则同时存在与，使相减 ，但为整数，故，得，从而注：如果取消，当或，不保证唯一经典方法：紧扣定义，构造法证存在性，反证法证唯一性证明2 只证存在性，用高斯记号，由有 ，记，故存在使证明3 只证存在性，作集合这是一个有下界的非空整数集，其中必有最小的，设时，有最小值再证，若不然，记，有即有比更小，这与为最小值矛盾故存在两个实数，使定理2 设是三个不全为0的整数，满足，其中也为整数，则证明 设的公约数， 的公约数任取，任取，得 有中元素的最大值中

9、元素的最大值，即注：这是辗转相除法求最大公约数的理论基础经典方法：要证明，只需证且定理3 对任意的正整数，有证明 因为是的公倍数，所以的最小公倍数也是的约数，存在使有 且为整数，故是的约数同理是的约数，即是的公约数下面证明，是的最大公约数若不然，有设，可见是的倍数，同样，是的倍数，即是的公倍数，则存在正整数使，有得 与矛盾，所以，得证注 也可以由，得，与矛盾两步可以交换吗？定理4 是两个不同时为0的整数，若是形如（是任意整数）的数中的最小正数，则（1）|；（2）证明 （1）由带余除法有得 ，知也是形如的非负数，但是形如的数中的最小正数，故，即 （2）由（1）有得是的公约数另一方面，的每一个公约

10、数都可以整除，所以是的最大公约数，推论若，则存在整数，使（很有用）定理5 互素的简单性质： （1）（2）（3）（4）若是一个素数，是任意一个整数，且不能被整除，则证明 因为，所以，素数的约数只有两种可能：但不能被整除，得推论 若是一个素数，是任意一个整数，则或（5）若，则存在整数，使（定理4推论）（6）若，则证明 由知存在整数，使有 ，得 （7）若，则， 证明 ，由（6）（8）若，则，其中为正整数证明 据（6），由可得 同样，由可得定理6 设是大于1的整数，则的除1之外的最小的正约数必是素数，且当是合数时，证明 用反证法，假设不是素数，则存在正整数数，使，但，故有，这与是的除1之外的最小正约数

11、矛盾，故是素数当是合数时，设，则也是的一个正约数，由的最小性得，从而，开方得定理7 素数有无穷多个，2是唯一的偶素数证明 假设素数只有有限多个，记为，作一个新数若为素数，则与素数只有 个矛盾若为合数，则必有，使，从而，又与矛盾综上所述，素数不能只有有限多个，所以素数有无穷多个2是素数，而大于2的偶数都是合数，所以2是唯一的偶素数注：这个证明中，包含着数学归纳法的早期因素：若假设有个素数，便有个素数（构造法、反证法）秒定理8（整除的性质）整数通常指非零整数（1），；当时， （2）若，则;若，则;若，且，则证明 由，有，得逆反命题成立“若，则”;由且得，又，得（3）若，且，则（4）若，则证明 （定

12、义法）由，有得 ，即 （5）若，则（6）若，则对任意整数，有证明 （定义法）由，有得 ，即 （7）若，且，则证明 由知存在整数，使，有 因为，所以整除等式的左边，进而整除等式的右边，即注意 不能由且得出如，但且（8）若，且，则证明 由知存在整数，使，有 又由有代入得所以 注意 不能由且得出如不能由且得出（9）若为素数，且，则或证明 若不然，则且，由为素数得，由互素的性质（6）得，再由为素数得，与矛盾注意 没有为素数，不能由推出或如，但且定义6 对于整数，且，若，则称关于模同余，记作；若，则称关于模不同余，记作 定理9（同余的性质）设为整数，（1）若且，则；证明 由且，有得（2）若且，则且证明

13、由且，有对直接相加 ，有得 .对分别乘以后相加，有得 （3）若，则对任意的正整数有且.（4）若，且对非零整数有，则证明 由、，有又，有均为整数，且得 定理10 设为整数，为正整数，（1）若，则（2）若，则（3）若，则定义7 设为正整数，为大于2的正整数, 是小于的非负整数，且若则称数为的进制表示定理11 给定整数，对任意的正整数，都有唯一的进制表示如，（10进制）（进制）定理12 （算术基本定理）每个大于1的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的其中为素数，为正整数 （分解唯一性）证明1 先证明，正整数可分解为素数的乘积 如果大于1的正整数为素数，命题已成立当正整数

14、为合数时，的正约数中必有一个最小的，记为，则为素数，有如果为素数，命题已成立当为合数时，的最小正约数为必为素数，有这个过程继续进行下去，由于为有限数，而每进行一步就要变小一次，于是，经过有限次后，比如次，就变为素数的乘积下面证明分解式是唯一的假设还有另一个分解式则有 因为等式的右边能被整除，所以左边也能被整除，于是整除中的某一个，但为素数，所以与相等，不妨设为，有把等式两边约去，得再重复上述步骤，又可得，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（），则有但均为素数，素数都大于1，有，这表明等式不可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的

15、 将分解式按的递增排列，并将相同的合并成指数形式，即得其中为素数，为正整数 证明2 用第二数学归纳法证明（1）当，因为2为素数，命题成立（2）假设命题对一切大于1而小于的正整数已成立这时，若为素数，命题成立；若不为素数，必存在，使由归纳假设，小于的可分解为素数的乘积得 ，适当调整的顺序，可得命题对于正整数成立由数学归纳法，命题对一切大于1的正整数成立下面证明分解式是唯一的假设的分解式不唯一，则至少有两个分解式得 有 且，这就存在，使且，但均为为素数，所以 又 ，所以 把等式两边约去，得再重复上述步骤，又可得，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（）

16、，则有但均为素数，素数都大于1，有，这表明上述等式不可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的将分解式按的递增排列，并将相同的合并成指数形式，即得其中为素数，为正整数 定理13 若正整数的素数分解式为 则的正约数的个数为，的一切正约数之和为证明 对于正整数，它的任意一个正约数可以表示为由于有共种取值，据乘法原理得的约数的个数为考虑乘积展开式的每一项都是的某一个约数（参见），反之，的每一个约数都是展开式的某一项，于是，的一切约数之和为注 构造法定义8 （高斯函数）对任意实数，是不超过的最大整数亦称为的整数部分，定理14 在正整数的素因子分解式中，素数作为因子出现的次数是证明 由于

17、为素数，故在中的次方数是各数中的次方数的总和（注意，若不为素数，这句话不成立）在中，有个的倍数；在个的倍数的因式中，有个的倍数；在个的倍数的因式中，有个的倍数；，如此下去，在正整数的素因子分解式中，素数作为因子出现的次数就为注 省略号其实是有限项之和画线示意中2的指数定理15 （费玛小定理）如果素数不能整除整数，则证明1 考察下面的个等式：由于素数不能整除整数，所以，不能整除每个等式的左边，得均不为0，只能取下面证明各不相等若不然，存在，使相减 应有素数整除，但素数不能整除，所以素数整除，然而由可得要素数整除是不可能的，得各不相等有再把上述个等式相乘，有即 ，其中是一个整数亦即 由于是素数，不

18、能整除，所以素数整除，得证证明2 改证等价命题：如果素数不能整除整数，则只需对证明成立，用数学归纳法（1），命题显然成立（2）假设命题对成立，则当时，由于，故有 （用了归纳假设）这表明，命题对是成立 由数学归纳法得又素数不能整除整数，有，得定义9 （欧拉函数）用表示不大于且与互素的正整数个数定理16 设正整数，则证明 用容斥原理设，记为中能被整除的数所组成的集合（），用表示中元素的个数，有易知，中与互素的正整数个数为由容斥原理得注 示意的容斥原理推论 对素数有定理17 整系数不定方程（）存在整数解的充分必要条件是证明 记（1）必要性（方程有解必须满足的条件）若方程存在整数解，记为，则由， 有，

19、得证（2）充分性（条件能使方程有解）若，可设由于形如的数中有最小正数满足两边乘以，得这表明方程有解定理18 若,，且是整系数不定方程的一个整数解，则方程的一切整数解可以表示为证明 直接代入知是方程的整数解，下面证明任意一个整数解都有的形式.由是方程的一个解，有又方程的任意一个解满足相减 但，故有有 得方程的任意一个整数解可以表示为定义10 （平面整点）在平面直角坐标系上，纵横坐标都是整数的点称为整点（也称格点）类似地可以定义空间整点第二讲 数论题的范例讲解主要讲几个重要类型：奇数与偶数，约数与倍数（素数与合数），平方数，整除，同余，不定方程，数论函数等重点是通过典型范例来分析解题思路、提炼解题

20、方法和巩固基本内容一、奇数与偶数整数按照能否被2整除可以分为两类，一类余数为0，称为偶数，一类余数为1，称为奇数偶数可以表示为，奇数可以表示为或一般地，整数被正整数去除，按照余数可以分为类，称为模的剩余类，从每类中各取出一个元素，可得模的完全剩余系（剩余类派出的一个代表团），称为模的非负最小完全剩余系.通过数字奇偶性质的分析而获得解题重大进展的技巧，常称作奇偶分析，这种技巧与分类、染色、数字化都有联系，在数学竞赛中有广泛的应用 关于奇数和偶数，有下面的简单性质： （1）奇数偶数（2）偶数的个位上是0、2、4、6、8；奇数的个位上是1、3、5、7、9（3）奇数与偶数是相间排列的；两个连续整数中必

21、是一个奇数一个偶数；（4）奇数个奇数的和是奇数；偶数个奇数的和是偶数；偶数跟奇数的和是奇数；任意多个偶数的和是偶数 （5）除2外所有的正偶数均为合数；（6）相邻偶数的最大公约数为2，最小公倍数为它们乘积的一半（7）偶数乘以任何整数的积为偶数（8）两数和与两数差有相同的奇偶性，（9）乘积为奇数的充分必要条件是各个因数为奇数（10）个偶数的积是的倍数（11）的充分必要条件是为偶数，的充分必要条件是为奇数（12）（13）任何整数都可以表示为例1 （1906，匈牙利）假设是的某种排列，证明：如果是奇数，则乘积是偶数解法1 （反证法）假设为奇数，则均为奇数，奇数个奇数的和还是奇数奇数=这与“奇数偶数”矛

22、盾 所以是偶数 评析 这个解法说明不为偶数是不行的，但没有指出为偶数的真正原因体现了整体处理的优点，但掩盖了“乘积”为偶数的实质解法2 （反证法）假设为奇数，则均为奇数，与的奇偶性相反，中奇数与偶数一样多，为偶数但已知条件为奇数，矛盾 所以是偶数评析 这个解法揭示了为偶数的原因是“为奇数”那么为什么“为奇数”时“乘积”就为偶数呢？解法3 中有个奇数，放到个括号，必有两个奇数在同一个括号，这两个奇数的差为偶数，得为偶数评析 这个解法揭示了为偶数的原因是“当为奇数时，中奇数与偶数个数不等，奇数多，某个括号必是两个奇数的差，为偶数”类似题： 例1-1（1986，英国）设是整数，是它们的一个排列，证明

23、是偶数（中奇数与偶数个数不等） 例1-2 的前24位数字为，记为该24个数字的任一排列，求证必为偶数（暗藏中奇数与偶数个数不等）例2 能否从中选出个数填入图的圆圈中，使得每两个有线相连的圈中的数相减（大数减小数），所得的14个差恰好为？解 考虑14个差的和，一方面为奇数另一方面，每两个数的差与其和有相同的奇偶性 ，因此，14个差的和的奇偶性与14个相应数之和的和的奇偶性相同，由于图中的每一个数与2个或4个圈中的数相加，对的贡献为或，从而为偶数，这与为奇数矛盾，所以不能按要求给图中的圆圈填数评析：用了计算两次的技巧对同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所求得的总和应

24、是相等的，这叫计算两次原理成富比尼原理计算两次可以建立左右两边关系不太明显的恒等式在反证法中，计算两次又可用来构成矛盾例3 有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？解 （1）4堆是不能保证的如4堆的奇偶性为：（反例） （奇奇），（偶偶），（奇偶），（偶奇）（2）5堆是可以保证 因为苹果和梨数的奇偶性有且只有上述4种可能，当把这些苹果和梨分成5堆时，必有2堆属于同一奇偶性，其和苹果数与梨数都是偶数例4 有个数，它们中的每一个要么是，要么是若，求证证明 由，有，再由知个中有一半是，有一半是，必为偶数，设现把个相乘，有

25、可见，为偶数，设，有，得证 例5 个整数，其积为，其和为0，试证证明 先证为偶数，若不然，由知，全为奇数，其和必为奇数，与其和为0（偶数），故必为偶数（中至少有1个偶数）再证为4的倍数，若不然，由为偶数知，恰有一个为偶数，其余个数全为奇数，奇数个奇数之和必为奇数，加上一个偶数，总和为奇数，与之和为0矛盾，所以，为4的倍数，（中至少有2个偶数）评析 要证，只须证中至少有2个偶数，分两步，第一步证至少有1个偶数，第二步证至少有2个偶数例6 在数轴上给定两点1和，在区间内任取个点，在此个点中，每相邻两点连一线段，可得条互不重叠的线段，证明在此条线段中，以一个有理点和一个无理点为端点的线段恰有奇数条证

26、明 将个点按从小到大的顺序记为，并在每一点赋予数值，使与此同时，每条线段也可数字化为（乘法）记的线段有条，一方面另一方面 得，故为奇数评析 用了数字化、奇偶分析的技巧二、约数与倍数最大公约数与最小公倍数的求法（1）短除法（2）分解质因数法设记 ，则 ，（3）辗转相除法例7 （1）求，；（2），解（1）方法1 分解质因数法由得 ，方法2 辗转相除法 或 或 （2）方法1 短除法由得 ，方法2 分解质因数法由得 ，例8 正整数分别除以得到的余数依次为，则的最小值为 解 依题意，对最小的，则是的公倍数得例9 有两个容器，一个容量为27升，一个容量为15升，如何利用它们从一桶油中倒出6升油来？解 相当

27、于求不定方程的整数解由知，存在整数，使可得一个解，从而方程即往小容器里倒2次油，每次倒满之后就向大容器里倒，大容器倒满时，小容器里剩有3升油；再重复一次，可得6升例10 对每一个，求证存在个互不相同的正整数，使，对任意的成立 证明 用数学归纳法当时，取，命题显然成立 假设时，命题成立，即存在，使 ，对任意的成立 现取为及它们每两个数之差的最小公倍数，则个数满足 即命题对时成立由数学归纳法知命题对成立 例11 证明对任意正整数，分数不可约证明1 （反证法）假若可约，则存在使 ，从而存在，使消去，得的 由（1）、（5）矛盾，得解题分析：（1）去掉反证法的假设与矛盾就是一个正面证法（2）式是实质性的

28、进展，表明可见 由此获得2个解法证明2 设存在，使消去，3-2，得得 证明3 由得 证明4 解题分析：第 相当于 -；第 相当于-2（-）=3-2；所以式与式的效果是一样的例12 不存在这样的多项式使得对任意的正整数，都是素数证明假设存在这样的多项式,对任意的正整数，都是素数，则取正整数，有素数使进而对任意的整数有（二项式定理展开）其中为整数，这表明为合数这一矛盾说明，不存在这样的多项式,对任意的正整数，都是素数三、平方数若是整数，则就叫做的完全平方数，简称平方数1平方数的简单性质（1）平方数的个位数只有6个：（2）平方数的末两位数只有22个：00，01，21，41，61，81，04，24，4

29、4，64，84，25，16，36，56，76，96，09，29，49，69，89 （3）（）（6）凡是不能被3整除的数，平方后被3除余1（7）在两个相邻整数的平方数之间，不能再有平方数（8）非零平方数的约数有奇数个（9）直角三角形的三边均为整数时，我们把满足的整数叫做勾股数勾股数的公式为其中为正整数，且一奇一偶这个公式可给出全部素勾股数2平方数的证明方法（1）反证法（2）恒等变形法（3）分解法设为平方数，且，则均为平方数（4）约数法证明该数有奇数个约数3非平方数的判别方法（1）若，则不是平方数（2）约数有偶数个的数不是平方数（3）个位数为2，3，7，8的数不是平方数（4）同余法：满足下式的数都

30、不是平方数（5）末两位数不是：00，01，21，41，61，81，04，24，44，64，84，25，16，36，56，76，96，09，29，49，69，89如个位数与十位数都是都是奇数的数，个位数是6、而十位数是偶数的数例13 有100盏电灯，排成一横行，从左到右，我们给电灯编上号码1，2，99，100每盏灯由一个拉线开关控制着最初，电灯全是关着的另外有100个学生，第一个学生走过来，把凡是号码为1的倍数的电灯的开关拉了一下；接着第2个学生走过来，把凡是号码为2的倍数的电灯的开关拉了一下；第3个学生走过来，把凡是号码为3的倍数的电灯的开关拉了一下，如此等等，最后那个学生走过来，把编号能被1

31、00整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的？讲解 （1）直接统计100次拉线记录，会眼花缭乱（2）拉电灯的开关有什么规律：电灯编号包含的正约数（学生）才能拉、不是正约数（学生）不能拉，有几个正约数就被拉几次（3）灯被拉的次数与亮不亮（开、关）有什么关系：0123456789关开关开关开关开关开 灯被拉奇数次的亮！（4）哪些数有奇数个约数：平方数（5）1100中有哪些平方数：共10个：1，4，9，16，25，36，49，64，81，100答案：编号为1，4，9，16，25，36，49，64，81，100共10个灯还亮例14 已知直角三角形的两条直角边分别为正整数，斜边为正整数，若

32、为素数，求证为平方数证明 由勾股定理，有但为素数，必有解得 ，从而 ，为平方数例15 求证，任意3个连续正整数的积不是平方数证明 设存在3个连续正整数（）的积为平方数，即存在整数，使即 ，但，故均为平方数，有得 ，（注意）这一矛盾说明，3个连续正整数的积不是平方数例16 设是异于2，5，13的任一整数求证在集合中可以找到两个不同元素，使得不是完全平方数证明 因为，所以不是完全平方数只能是若结论不成立，则存在正整数，使同时成立，由知是奇数，设代入得为奇数，代入、知均为偶数设，代入、后相减，有 由于为偶数，故同奇偶，可被4整除，得为偶数这与上证为奇数矛盾所以，在集合中可以找到两个不同元素，使得不是

33、完全平方数例17 ()设为正整数，整除证明是完全平方数证明令，是正整数式中是对称的，不妨设(l)若，则本题获证(2)若，由带余除法定理，可设（是整数)，则为正整数，由 且 得 ， 所以必有， 化简 ，得 ， 于是 ，其中此时若，则，本题获证若，可继续令（是整数），仿上可推得此时若，则，本题获证若，可如上法做下去因，且均为整数故总能得到某个，使，是完全平方数综上本题获证这种证明的方法叫“无穷递降法”，是17世纪法国数学家费马(Fermat1601一1665)首创和应用的一种方法 四整除整除的判别方法主要有7大类1定义法证，有三种方式（1）假设，然后证明（定理4）（2）具体找出，满足（3）论证的存

34、在例18 任意一个正整数与它的十进制表示中的所有数码之差能被9整除 证明 设，其中，则按定义 2数的整除判别法（1）任何整数都能被1整除（2）如果一个整数的末位能被2或整除，那么这个数就能被2或整除 （3）如果一个整数的末两位能被或25整除，那么这个数就能被4或25整除 （4）如果一个整数的末三位能被8或125整除，那么这个数就能被8或125整除 （5）如果一个整数各数位上的数字之和能被3或9整除，那么这个数就能被3或9整除证明 由，有 （6）如果一个整数的末三位数与末三位数以前的数字所组成的数的差能被7或11或13整除，那么这个数就能被7或11或13整除 证明 由 知 ， 又由，而均为素数知

35、，能被7或11或13整除（7）如果一个整数的奇位数字之和与偶位数字之和的差能被11整除，则这个数能被11整除证明 由，有3分解法主要用乘法公式如例19 试证证明 改证设，则得又 得但，得，即例20 设与为正整数，满足求证可被1979整除（1979）证明 得1979整除，但1979为素数，得可被1979整除例20-1 2009年9月9日的年、月、日组成“长长久久、永不分离”的吉祥数字20090909，而它也恰好是一个不能再分解的素数若规定含素因子的数为吉祥数，请证明最简分数的分子是吉祥数证明：由其中为正整数，有这表明，整除，但为素数，不能整除，所以整除，得是吉祥数4 余数分类法例21 试证证明1

36、 任何整数被3除其余数分为3类（1）时，有有（2）时，有有（3）有综上得，证明2 ，得 ，又，得5数学归纳法6反证法7构造法例22 个连续整数中必有一个能被整除证明 设个连续整数为若这个数被除没有一个余数为0，则这个数的余数只能取，共种情况，必存在两个数使 其中，相减有 ，即 与矛盾故个连续整数中必有一个能被整除也可以由得推出，与为整数矛盾例23 个连续整数之积必能被整除证明 设个连续整数为（1）若这个连续整数为正整数，则只须证明，对任何一个素数，分子中所含的方次不低于分母中所含的方次，由高斯函数的性质，有得为整数（证实了组合数的实际意义）（2）若这个连续整数中有0，则连乘积为0，必能被整除（

37、3）若这个连续整数为负整数，则由（1）知为整数，故为整数例24 有男孩、女孩共个围坐在一个圆周上（），若顺序相邻的3人中恰有一个男孩的有组，顺序相邻的3人中恰有一个女孩的有组，求证证明 现将小孩记作，且数字化则“3人组”数值化为其中又设取值为3的有个，取值为的有个，依题意，取值为1的有个，取值为的有个，得可见例25 （1956，中国北京）证明对任何正整数都是整数，并且用3除时余2分析 只需说明为整数，但不便说明“用3除时余2”，应说明是3的倍数作变形命题可证 证明 已知即因为相邻2个整数必有偶数，所以为整数又可变为因为相邻3个整数必有3的倍数，故能被3整除；又，所以能被3整除；得用3除时余2五

38、、同余根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解题例26 正方体的顶点标上或，面上标上一个数，它等于这个面四个顶点处的数的乘积，求证，这样得出的14个数之和不能为0证明 记14个数的和为，易知，这14个数不是就是，若八个顶点都标上，则，命题成立对于顶点有的情况，我们改变为，则和中有4的数改变了符号，用表示改变后的和，由知 ， 这表明，改变一个，和关于模4的余数不变，重复进行，直到把所有的都改变为，则所以，例27 设多项式的系数都是整数，并且有一个奇数及一个偶数使得及都是奇数，求证方程没有整数根 证明 由已知有若方程存在整数根，即当为奇数时，有与矛盾有为

39、偶数时，有与矛盾所以方程没有整数根六、不定方程未知数的个数多于方程个数的整系数代数方程，称为不定方程求不定方程的整数解，叫做解不定方程 解不定方程通常要解决3个问题，方程是否有解？有解时，有几个解，解数是有限还是无穷？求出全部解例28 解方程解法1 由知方程有整数解 观察特解，列表12325得一个特解从而通解为方法总结：第1步，验证，经常是第2步，求特解（观察、列举、辗转相除等）第3步，代入公式解法2 由知方程有整数解用辗转相除法求特解，再得通解先求的一个解，由逆过来有同乘以213，有得 解法3 由知方程有整数解用柯西方法求特解，将方程变为令为整数，有令为整数，有代入得方法总结：第1步，将系数

40、较小的那个未知数用另一个未知数来表示第2步，将表达式形式分离为整数部分与分数部分（实际上也是整数）设分数部分为，又得一个不定方程第3步，重复上述步骤，设逐次的分数部分为，那么方程的系数越来越小；对，经过有限次操作，最后方程的两个未知数中必有一个系数为1，从而得到，（为整数）第4步，将上式按顺序倒代上去，逐步求出，即得不定方程整数解得通解解法4 用同余法，由有但，有得 ，进而 方法总结：或例29 求方程的整数解解 由2009的分解式，有有 例30 甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，直到有一方队员全被淘汰为止，另一方

41、获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数为 （1988，高中联赛）解法1 设甲、乙两队的队员按出场顺序分别为和如果甲方获胜，设获胜的场数是，则而且 容易证明以下两点：在甲方获胜时（i）不同的比赛过程对应着方程的不同非负整数解；（ii）方程的不同非负整数解对应着不同的比赛过程，例如，解（2，0，0，1，3，1，0）对应的比赛过程为：胜和；胜、和；胜后负于；胜、和但负于；最后胜结束比赛下面求方程的非负整数解个数，设，问题等价于方程正整数解的个数，将上式写成从13个加号取6个的方法数种得甲方获胜的不同的比赛过程有种同理，乙方获胜的不同的比赛过程也有种，合计种比赛过程解法2设甲、乙两队的队员按出场顺序分别为和每一个比赛过程对应着这14个元素的一个排列，且满足的下标从左到右是递增的，的下标从左到右也是递增的由于从14个位置中取出7个来，有序地排上有种排法，而剩下的7个位置有序地排上只有一种排法，所