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

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

1、数学竞赛中的数论问题 罗增儒引言数论的相识：数论是关于数的学问，主要探讨整数，重点对象是正整数，对中学生可以说，数论是探讨正整数的一个数学分支什么是正整数呢？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描绘，正整数1，2，3，是这样一个集合：（1）有一个最小的数1 （2）每一个数的后面都有且只有一个后继数；除1之外，每一个数的都是且只是一个数的后继数这个构造很像数学归纳法，事实上，有这样的归纳公理：（3）对的子集，若，且当时，有后继数，则就是这么一个简洁的数集，里面却有无穷无尽的奇妙，有的奇妙甚至使得人们疑心：人类的才智还没有成熟到解决它的程度比方，哥德巴赫猜测：174

2、2年6月7日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数，由4开场，都可以表示为两个素数和的形式，任何奇数，由7开场，都可以表示为三个素数的和后者是前者的推论，也可独立证明（已解决）“表示为两个素数和的形式”就是闻名的哥德巴赫猜测，简称1+1欧拉认为这是对的，但证不出来1900年希尔伯特将其归入23个问题中的第8个问题1966年陈景润证得：一个素数+素数素数（1+2），至今仍无人超越陈景润的数学老师沈元很重视利用名人、名言、名事去鼓励学生，他曾屡次在开讲时，说过这样的话:“自然科学的皇后是数学，数学的皇冠是数论，哥德巴赫猜测则是皇冠上的明珠”陈景润就是由此而受到了启示和鼓励，绽

3、开了艰辛卓绝的终生奋斗和绚丽辉煌的奋斗终生，离摘取“皇冠上的明珠”仅一步之遥数论题涉与的学问不是许多，但用不多的学问来解决问题往往就须要较强的实力和精明多的技巧，有人说：用以发觉数学人才，在初等数学中再也没有比数论教材更好的课程了任何学生如能把当今一本数论教材中的练习做出，就应当受到鼓励，劝他（她）将来去从事数学方面的工作（UDudley数论根底前言）下面，是一个好玩的故事当代最高产的数学家厄尔多斯听说一个叫波萨（匈牙利，1948）的小男孩很聪慧，就问了他一个问题加以考察（1959）：假如你手头上有个正整数，这些正整数小于或等于，那么你肯定有一对整数是互素的，你知道这是什么缘由吗？不到12岁的

4、波萨只用了1分半钟，就给出了问题的解答他将1分成（1，2），（3，4），（）共个抽屉，手头的个正整数肯定有两个属于同一抽屉，这两个数是相邻的正整数，必定互素通过这个问题，厄尔多斯认定波萨是个难得的英才，就细心加以培育，不到两年，14岁的波萨就发表了图论中“波萨定理”重视数学实力的数学竞赛，已经广泛采纳数论题目，是数学竞赛四大支柱之一，四大支柱是：代数，几何，初等数论，组合初步（俗称代数题、几何题、算术题和智力题）高中竞赛加试四道题正好是四大模块各一题，分别是几何题、代数题、数论题、组合题，一试中也会有数论题数论受到数学竞赛的青睐可能还有一个技术上的缘由，就是它能便利地供应从小学到高校各个层面的

5、、簇新而好玩的题目数论题的主要类型：在初中竞赛大纲中，数论的内容列有：十进制整数与表示方法；整除性，被2、3、4、5、8、9、11等数整除的断定；素数和合数，最大公约数与最小公倍数；奇数和偶数，奇偶性分析；带余除法和利用余数分类；完全平方数；因数分解的表示法，约数个数的计算； 简洁的一次不定方程 在高中竞赛大纲中，数论的内容列有：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数，费马小定理，格点与其性质，无穷递降法，欧拉定理，孙子定理依据已出现的试题统计，中学数学竞赛中的数论问题的主要有8个重点类型：（1）奇数与偶数（奇偶分析法、01法）；（2）约数与倍数、素数与

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

7、数，记作 中的没有依次，最大公约数也称最大公因数简洁性质：一个功能：可以把对整数的探讨转化为对非负整数的探讨定义3 （最小公倍数）非零整数的最小公倍数是能被其中每一个所整除的最小正整数，记作简洁性质：假如是正整数的公倍数，则存在正整数使证明若不然，有（），由都是的公倍数得也是的公倍数，但，与的最小性冲突故定义4 假如整数 满意，则称与是互素的（也称互质）定义5 大于1且除1与其自身外没有别的正整数因子的正整数，称为素数（也称质数）其余大于1的正整数称为合数；数1既不是素数也不是合数定理1 若是两个整数，则存在两个实数，使，并且是唯一性证明1 先证存在性作序列则必在上述序列的某两项之间，从而存在

8、一个整数，使 ，即 ，取 ， ，得 ，即存在两个实数，使 再证唯一性假设不唯一，则同时存在与，使 ， ，相减 ， ， ，但为整数，故，得，从而注：假如取消，当或，不保证唯一经典方法：紧扣定义，构造法证存在性，反证法证唯一性证明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 （高斯函数）对随意实数，是不超过的最大整数亦称为的整

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

18、数整除是不行能的，得各不相等有 再把上述个等式相乘，有 ，即 ，其中是一个整数亦即 由于是素数，不能整除，所以素数整除，得证 证明2 改证等价命题：假如素数不能整除整数，则只需对证明成立，用数学归纳法（1），命题明显成立（2）假设命题对成立，则当时，由于，故有 （用了归纳假设）这说明，命题对是成立 由数学归纳法得又素数不能整除整数，有，得定义9 （欧拉函数）用表示不大于且与互素的正整数个数定理16 设正整数，则 证明 用容斥原理设，记为中能被整除的数所组成的集合（），用表示中元素的个数，有，易知，中与互素的正整数个数为 ，由容斥原理得 注 示意的容斥原理推论 对素数有定理17 整系数不定方程（

19、）存在整数解的充分必要条件是证明 记（1）必要性（方程有解必需满意的条件）若方程存在整数解，记为，则，由， 有，得证（2）充分性（条件能使方程有解）若，可设由于形如的数中有最小正数满意两边乘以，得 这说明方程有解定理18 若,，且是整系数不定方程的一个整数解，则方程的一切整数解可以表示为 证明 干脆代入知是方程的整数解，下面证明随意一个整数解都有的形式.由是方程的一个解，有， 又方程的随意一个解满意 ， 相减 但，故有 ，有 得方程的随意一个整数解可以表示为 定义10 （平面整点）在平面直角坐标系上，纵横坐标都是整数的点称为整点（也称格点）类似地可以定义空间整点第二讲 数论题的范例讲解主要讲几

20、个重要类型：奇数与偶数，约数与倍数（素数与合数），平方数，整除，同余，不定方程，数论函数等重点是通过典型范例来分析解题思路、提炼解题方法和稳固根本内容一、奇数与偶数整数依据能否被2整除可以分为两类，一类余数为0，称为偶数，一类余数为1，称为奇数偶数可以表示为，奇数可以表示为或一般地，整数被正整数去除，依据余数可以分为类，称为模的剩余类，从每类中各取出一个元素，可得模的完全剩余系（剩余类派出的一个代表团），称为模的非负最小完全剩余系.通过数字奇偶性质的分析而获得解题重大进展的技巧，常称作奇偶分析，这种技巧与分类、染色、数字化都有联络，在数学竞赛中有广泛的应用 关于奇数和偶数，有下面的简洁性质：

21、（1）奇数偶数（2）偶数的个位上是0、2、4、6、8；奇数的个位上是1、3、5、7、9（3）奇数与偶数是相间排列的；两个连续整数中必是一个奇数一个偶数；（4）奇数个奇数的和是奇数；偶数个奇数的和是偶数；偶数跟奇数的和是奇数；随意多个偶数的和是偶数 （5）除2外全部的正偶数均为合数；（6）相邻偶数的最大公约数为2，最小公倍数为它们乘积的一半（7）偶数乘以任何整数的积为偶数（8）两数和与两数差有一样的奇偶性，（9）乘积为奇数的充分必要条件是各个因数为奇数（10）个偶数的积是的倍数（11）的充分必要条件是为偶数，的充分必要条件是为奇数（12）（13）任何整数都可以表示为例1 （1906，匈牙利）假设

22、是的某种排列，证明：假如是奇数，则乘积 是偶数解法1 （反证法）假设为奇数，则均为奇数，奇数个奇数的和还是奇数奇数=，这与“奇数偶数”冲突 所以是偶数 评析 这个解法说明不为偶数是不行的，但没有指出为偶数的真正缘由表达了整体处理的优点，但掩盖了“乘积”为偶数的本质解法2 （反证法）假设为奇数，则均为奇数，与的奇偶性相反，中奇数与偶数一样多，为偶数但已知条件为奇数，冲突 所以是偶数评析 这个解法提醒了为偶数的缘由是“为奇数”那么为什么“为奇数”时“乘积”就为偶数呢？解法3 中有个奇数，放到个括号，必有两个奇数在同一个括号，这两个奇数的差为偶数，得为偶数评析 这个解法提醒了为偶数的缘由是“当为奇数

23、时，中奇数与偶数个数不等，奇数多，某个括号必是两个奇数的差，为偶数”类似题： 例1-1（1986，英国）设是整数，是它们的一个排列，证明是偶数（中奇数与偶数个数不等） 例1-2 的前24位数字为，记为该24个数字的任一排列，求证必为偶数（暗藏中奇数与偶数个数不等）例2 能否从中选出个数填入图的圆圈中，使得每两个有线相连的圈中的数相减（大数减小数），所得的14个差恰好为？解 考虑14个差的和，一方面为奇数另一方面，每两个数的差与其和有一样的奇偶性 ，因此，14个差的和的奇偶性与14个相应数之和的和的奇偶性一样，由于图中的每一个数与2个或4个圈中的数相加，对的奉献为或，从而为偶数，这与为奇数冲突，

24、所以不能按要求给图中的圆圈填数评析：用了计算两次的技巧对同一数学对象，当用两种不同的方式将整体分为局部时，则按两种不同方式所求得的总和应是相等的，这叫计算两次原理成富比尼原理计算两次可以建立左右两边关系不太明显的恒等式在反证法中，计算两次又可用来构成冲突例3 有一大筐苹果和梨分成若干堆，假如你肯定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？解 （1）4堆是不能保证的如4堆的奇偶性为：（反例） （奇奇），（偶偶），（奇偶），（偶奇）（2）5堆是可以保证 因为苹果和梨数的奇偶性有且只有上述4种可能，当把这些苹果和梨分成5堆时，必有2堆属于同一奇偶性，其和苹果

25、数与梨数都是偶数例4 有个数，它们中的每一个要么是，要么是若，求证证明 由，有，再由，知个中有一半是，有一半是，必为偶数，设现把个相乘，有 ，可见，为偶数，设，有，得证 例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 正整数分别除以得到的余数依次

27、为，则的最小值为 解 依题意，对最小的，则是的公倍数，得例9 有两个容器，一个容量为27升，一个容量为15升，如何利用它们从一桶油中倒出6升油来？解 相当于求不定方程的整数解由知，存在整数，使，可得一个解，从而方程 即往小容器里倒2次油，每次倒满之后就向大容器里倒，大容器倒满时，小容器里剩有3升油；再重复一次，可得6升例10 对每一个，求证存在个互不一样的正整数，使，对随意的成立 证明 用数学归纳法当时，取，命题明显成立 假设时，命题成立，即存在，使 ，对随意的成立 现取为与它们每两个数之差的最小公倍数，则个数 满意 即命题对时成立由数学归纳法知命题对成立 例11 证明对随意正整数，分数不行约

28、证明1 （反证法）假如可约，则存在， 使 ，从而存在，使消去，得 ， 的 由（1）、（5）冲突，得解题分析：（1）去掉反证法的假设与冲突就是一个正面证法（2）式是本质性的进展，说明 ，可见 由此获得2个解法证明2 设存在，使消去，3-2，得 得 证明3 由得 证明4 解题分析：第 相当于 -；第 相当于-2（-）=3-2；所以式与式的效果是一样的例12 不存在这样的多项式 ，使得对随意的正整数，都是素数证明假设存在这样的多项式,对随意的正整数，都是素数，则取正整数，有素数使 ，进而对随意的整数有 （二项式定理绽开），其中为整数，这说明为合数这一冲突说明，不存在这样的多项式,对随意的正整数，都是

29、素数三、平方数若是整数，则就叫做的完全平方数，简称平方数1平方数的简洁性质（1）平方数的个位数只有6个：（2）平方数的末两位数只有22个：00，01，21，41，61，81，04，24，44，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）分解法设为平方数，且

30、，则均为平方数（4）约数法证明该数有奇数个约数3非平方数的判别方法（1）若，则不是平方数（2）约数有偶数个的数不是平方数（3）个位数为2，3，7，8的数不是平方数（4）同余法：满意下式的数都不是平方数， ， ， ，（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个学生，第一个学生走过来，把但

31、凡号码为1的倍数的电灯的开关拉了一下；接着第2个学生走过来，把但凡号码为2的倍数的电灯的开关拉了一下；第3个学生走过来，把但凡号码为3的倍数的电灯的开关拉了一下，如此等等，最终那个学生走过来，把编号能被100整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的？讲解 （1）干脆统计100次拉线记录，会纷繁芜杂（2）拉电灯的开关有什么规律：电灯编号包含的正约数（学生）才能拉、不是正约数（学生）不能拉，有几个正约数就被拉几次（3）灯被拉的次数与亮不亮（开、关）有什么关系：0123456789关开关开关开关开关开 灯被拉奇数次的亮！（4）哪些数有奇数个约数：平方数（5）1100中有哪些平方数：共1

32、0个：1，4，9，16，25，36，49，64，81，100答案：编号为1，4，9，16，25，36，49，64，81，100共10个灯还亮例14 已知直角三角形的两条直角边分别为正整数，斜边为正整数，若为素数，求证为平方数证明 由勾股定理，有 ，但为素数，必有 解得 ，从而 ，为平方数例15 求证，随意3个连续正整数的积不是平方数证明 设存在3个连续正整数（）的积为平方数，即存在整数，使 ，即 ，但，故均为平方数，有得 ，（留意）这一冲突说明，3个连续正整数的积不是平方数例16 设是异于2，5，13的任一整数求证在集合中可以找到两个不同元素，使得不是完全平方数证明 因为，所以不是完全平方数只

33、能是若结论不成立，则存在正整数，使同时成立，由知是奇数，设代入得 为奇数，代入、知均为偶数设，代入、后相减，有 由于为偶数，故同奇偶，可被4整除，得为偶数这与上证为奇数冲突所以，在集合中可以找到两个不同元素，使得不是完全平方数例17 ()设为正整数，整除证明是完全平方数证明令，是正整数式中是对称的，不妨设(l)若，则本题获证(2)若，由带余除法定理，可设（是整数)，则为正整数，由 且 得 ， 所以必有， 化简 ，得 ， 于是 ，其中此时若，则，本题获证若，可接着令（是整数），仿上可推得，此时若，则，本题获证若，可如上法做下去因，且均为整数故总能得到某个，使，是完全平方数综上本题获证这种证明的方

34、法叫“无穷递降法”，是17世纪法国数学家费马(Fermat1601一1665)首创和应用的一种方法 四整除整除的判别方法主要有7大类1定义法证，有三种方式（1）假设，然后证明（定理4）（2）详细找出，满意（3）论证的存在例18 随意一个正整数与它的十进制表示中的全部数码之差能被9整除 证明 设，其中，则 按定义 2数的整除判别法（1）任何整数都能被1整除（2）假如一个整数的末位能被2或整除，那么这个数就能被2或整除 （3）假如一个整数的末两位能被或25整除，那么这个数就能被4或25整除 （4）假如一个整数的末三位能被8或125整除，那么这个数就能被8或125整除 （5）假如一个整数各数位上的数

35、字之和能被3或9整除，那么这个数就能被3或9整除证明 由，有， （6）假如一个整数的末三位数与末三位数以前的数字所组成的数的差能被7或11或13整除，那么这个数就能被7或11或13整除 证明 由 ，知 ， 又由，而均为素数知，能被7或11或13整除（7）假如一个整数的奇位数字之和与偶位数字之和的差能被11整除，则这个数能被11整除证明 由，有3分解法主要用乘法公式如例19 试证证明 改证设，则 得又 得但，得，即例20 设与为正整数，满意 ，求证可被1979整除（1979）证明 得1979整除，但1979为素数，得可被1979整除例20-1 2009年9月9日的年、月、日组成“长许久久、永不分

36、别”的祥瑞数字20090909，而它也恰好是一个不能再分解的素数若规定含素因子的数为祥瑞数，请证明最简分数的分子是祥瑞数证明：由其中为正整数，有 ，这说明，整除，但为素数，不能整除，所以整除，得是祥瑞数4 余数分类法例21 试证证明1 任何整数被3除其余数分为3类 ，（1）时，有 有（2）时，有有（3）有综上得，证明2 ，得 ，又，得5数学归纳法6反证法7构造法例22 个连续整数中必有一个能被整除证明 设个连续整数为 ，若这个数被除没有一个余数为0，则这个数的余数只能取，共种状况，必存在两个数 ，使 其中，相减 ，有 ，即 与冲突故个连续整数中必有一个能被整除也可以由得 ，推出，与为整数冲突例23 个连续整数之积必能被整除证明 设个连续整数为 ，（1）若这个连续整数为正整数，则 只须证明，对任何一个素数，分子中所含的方次不低于分母中所含的方次，由高斯函数的性质，有 得为整数（证明了组合数的实际意义）（2）若这个连续整数中有0，则连乘积为0，必能被整除（3）若这个连续整数为负整数，则 由（1）知为整数，故为整数例24 有男孩、女孩共个围坐在一个圆周上（），若依次相邻的3人中恰有一个男孩的有组，依次相邻的3人中恰有一个女孩的有组，求证证明 现将小孩记作，且数字化 则“3人组”数值化为