数学竞赛中的数论问题(20220320111507).pdf

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

1、1 数学竞赛中的数论问题罗增儒引言数论的认识：数论是关于数的学问，主要研究整数，重点对象是正整数，对中学生可以说，数论是研究正整数的一个数学分支什么是正整数呢？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描述，正整数1，2，3，是这样一个集合N：（1）有一个最小的数1（2）每一个数a的后面都有且只有一个后继数/a；除 1 之外，每一个数的都是且只是一个数的后继数这个结构很像数学归纳法，事实上，有这样的归纳公理：（3）对N的子集M，若1M，且当aM时，有后继数/aM，则MN就是这么一个简单的数集，里面却有无穷无尽的奥秘，有的奥秘甚至使得人们怀疑：人类的智慧还没有成熟到解决

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

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

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

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

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

7、0r时，则称a被b整除，记作b a，或者说a是b的倍数，而b是a的约数（,q r的存在性由定理1 证明）定义2（最大公约数）设整数12,na aa中至少有一个不等于零，这n个数的最大公约数是能整除其中每一个整数的最大正整数，记作12,na aa12,na aa中的ia没有顺序，最大公约数也称最大公因数简单性质：1212,nna aaaaa一个功能：可以把对整数的研究转化为对非负整数的研究定义3（最小公倍数）非零整数12,na aa的最小公倍数是能被其中每一个1iain所整除的最小正整数，记作12,na aa简单性质：如果k是正整数,a b的公倍数，则存在正整数m使,km a b证明若不然，有,

8、km a br（0,ra b），由,k a b都是,a b的公倍数得r也是,a b的公倍数，但0,ra b，与,a b的最小性矛盾故,km a b定义 4如果整数,a b满足,1a b，则称a与b是互素的（也称互质）定义 5大于 1 且除 1 及其自身外没有别的正整数因子的正整数，称为素数（也称质数）其余大于1 的正整数称为合数；数1 既不是素数也不是合数定理 1 若,a b是两个整数，0b，则存在两个实数,q r，使0aqbrrb，并且,q r是唯一性证明 1先证存在性作序列,3.2,0,2,3,bbbbbb则a必在上述序列的某两项之间，从而存在一个整数q，使1qbaqb，4 即0aqbb，

9、取raqb，0rb，得aqbr，即存在两个实数,q r，使0aqbrrb再证唯一性假设不唯一，则同时存在11,q r与12,q r，使1110aqbrrb，2220aq brrb，相减1221qqbrr，1221qq brrb，1201qq，但12qq为整数，故120qq，得12qq，从而12rr注：如果取消0rb，当0r或rb，不保证唯一经典方法：紧扣定义，构造法证存在性，反证法证唯一性证明 2 只证存在性，用高斯记号，由01aabb，有0aabbb，记arabb，故存在,0aaqrabrbbb使0aqbrrb证明 3只证存在性，作集合|,0Mabx xZ abx这是一个有下界的非空整数集，

10、其中必有最小的，设xq时，有最小值r0raqbr再证rb，若不然，rb，记1rbr，有5 111aqbrqbbrb qr11rab qM即M有1r比r更小，这与r为最小值矛盾故存在两个实数,q r，使0aqbrrb定理2 设,a b c是三个不全为0 的整数，满足aqbc，其中q也为整数，则,a bb c证明设A,a b的公约数，B,b c的公约数任取|d ad cabqdAdBABd bd b，任取|d bd bdBdABAd cd abqc，得AB有A中元素的最大值B中元素的最大值，即,a bb c注：这是辗转相除法求最大公约数的理论基础经典方法：要证明AB，只需证AB且BA定理 3对任意

11、的正整数,a b，有,a ba bab证明因为ab是,a b的公倍数，所以,a b的最小公倍数也是ab的约数，存在q使,abq a b，有,a baqb且,a bb为整数，故q是a的约数同理q是b的约数，即q是,a b的公约数下面证明，q是,a b的最大公约数若不然，,qa b有,abq a ba ba b6 设,abbkaa ba b，可见k是a的倍数，同样,abakba ba b，k是b的倍数，即k是,a b的公倍数，则存在正整数m使,km a b，有,abm a ba ba b，得,abq a ba ba b与矛盾，所以，,qa b，得证,a ba bab注也可以由,1,aba bkqm

12、aba ba bq，得,qa b，与,qa b矛盾两步,abq a baba b k可以交换吗？定理 4 ,a b是两个不同时为0 的整数，若00axby是形如axby（,x y是任意整数）的数中的最小正数，则（1）00axby|axby；（2）00axby,a b证明（1）由带余除法有00axbyaxbyqr，000raxby，得0000ra xqxxb yqyaxby，知r也是形如axby的非负数，但00axby是形如axby的数中的最小正数，故0r，即00axby|axby（2）由（1）有00axby|10aba，00axby|01abb，得00axby是,a b的公约数另一方面，,a

13、b的每一个公约数都可以整除00axby，所以00axby是,a b的最大公约数，00axby,a b7 推论若,1a b，则存在整数,s t，使1asbt（很有用）定理 5互素的简单性质：（1）1,1a（2）,11n n（3）21,211nn（4）若p是一个素数，a是任意一个整数，且a不能被p整除，则,1a p证明因为,|a pp，所以，素数p的约数只有两种可能：,1,a pa pp但a不能被p整除，,a pp，得,1a p推论若p是一个素数，a是任意一个整数，则,1a p或,a pp（5）若,1a b，则存在整数,s t，使1asbt（定理 4 推论）（6）若,1,1a ba c，则,1a

14、bc证明由,1a b知存在整数,s t，使1asbt有a csbctc，得,1a bca c（7）若,1a b，则,1ab a，,1ab b，,1ab ab证明,1ab ab ab a，,1ab ba b，由（6）,1ab ab（8）若,1a b，则,1mnab，其中,m n为正整数证明据（6），由,1a b可得,1mab同样，由,1mab可得,1mnab定理 6 设a是大于 1 的整数，则a的除 1 之外的最小的正约数q必是素数，且当a是合数时，qa8 证明用反证法，假设q不是素数，则存在正整数数1q，11qq，使1|qq，但|q a，故有1|qa，这与q是a的除 1 之外的最小正约数矛盾，

15、故q是素数当a是合数时，设1aa q，则1a也是a的一个正约数，由q的最小性得1qa，从而21qa qa，开方得qa定理 7素数有无穷多个，2 是唯一的偶素数证明假设素数只有有限多个，记为12,nppp，作一个新数1211npppp若p为素数，则与素数只有n个12,nppp矛盾若p为合数，则必有12,inpppp，使|ipp，从而|1ip，又与1ip矛盾综上所述，素数不能只有有限多个，所以素数有无穷多个2 是素数，而大于2 的偶数都是合数，所以2 是唯一的偶素数注：这个证明中，包含着数学归纳法的早期因素：若假设有n个素数，便有1n个素数（构造法、反证法）秒定理 8（整除的性质）整数,a b c

16、通常指非零整数（1）1 a，1|a；当0a时，|a a，|0a（2）若b a，0a，则ba;若b a，ba，则0a;若0ab，且,ba ab，则ab证明由b a，0a，有abq，得ab qb逆反命题成立“若b a，ba，则0a”;由ba且ba得ab，又0ab，得ab（3）若abcd，且|,|,|e a e b e c，则|e d（4）若c b，b a，则c a证明（定义法）由c b，b a，有12,bq c aq b，得12aq qc，9 即c a（5）若c a，则bc ab（6）若c a，c b，则对任意整数,m n，有c manb证明（定义法）由c a，c b，有12,aq c bq c，

17、得12manbmqnqc，即c manb（7）若,1a b，且a bc，则a c证明由,1a b知存在整数,s t，使1asbt，有a csbc tc，因为a a，a bc，所以a整除等式的左边，进而整除等式的右边，即a c注意不能由a bc且|ab得出a c如6 4 9，但6|4且6|9（8）若,1a b，且,a c b c，则ab c证明由,1a b知存在整数,s t，使1asbt，有acsbctc，又由,a c b c有12,caq cbq代入得21ab q sab q tc，所以ab c注意不能由a c且b c得出ab c如不能由6 30且10|30得出60|30（9）若a为素数，且a

18、 bc，则a b或a c证明若不然，则|ab且|ac，由a为素数得,1,1a ba c，由互素的性质（6）得,1a bc，再由a为素数得|abc，与a bc矛盾注意没有a为素数，不能由a bc推出a b或a c如6 4 9，但6|4且6|910 定义6对于整数,a b c，且0c，若()c ab，则称,a b关于模c同余，记作(mod)abc；若|cab，则称,a b关于模c不同余，记作a(mod)bc定理 9（同余的性质）设,a b c d m为整数，0,m（1）若(mod)abm且(mod)bcm，则(mod)acm；证明由(mod)abm且(mod)bcm，有12,abmq bcmq，1

19、2acm qq，得(mod)acm（2）若(mod)abm且(mod)cdm，则(m o d)a c b dm且(mod)acbdm证明由(mod)abm且(mod)cdm，有12,abmq cdmq，对直接相加，有12acbdm qq，得(mod)acbdm.对分别乘以,c b后相加，有12acbdacbcbcbdm cqbq，得(mod)acbdm（3）若(mod)abm，则对任意的正整数n有(mod)nnabm且(mod)anbnmn.（4）若(mod)abm，且对非零整数k有(,)k a b m，则modabmkkk证明由(mod)abm、，有abmq，又(,)k a b m，有,a

20、b mk k k均为整数，且11 abmqkkk，得modabmkkk定理 10 设,a b为整数，n为正整数，（1）若ab，则nnabab123221nnnnnnnababaabababb（2）若ab，则2121nnabab212122232422322nnnnnnnababaabababb（3）若ab，则22nnabab2221222322221nnnnnnnababaabababb定义 7设n为正整数，k为大于 2 的正整数,12,ma aa是小于k的非负整数，且10a若12121mmmmna ka kaka，则称数12ma aa为n的k进制表示定理 11给定整数2k，对任意的正整数n，

21、都有唯一的k进制表示如12121101010mmmmnaaaa，109,0iaa（10 进制）12121222mmmmnaaaa101,0iaa（进制）定理 12（算术基本定理）每个大于1 的正整数都可分解为素数的乘积，而且不计因数的顺序时，这种表示是唯一的1212kknppp，其中12kppp为素数，12,k为正整数（分解唯一性）证明 1 先证明，正整数n可分解为素数的乘积12mnp pp如果大于 1 的正整数n为素数，命题已成立当正整数n为合数时，n的正约数中必有一个最小的，记为1p，则1p为素数，有12 11np a，11an如果1a为素数，命题已成立当1a为合数时，1a的最小正约数2p

22、为必为素数，有11122np ap p a，211aan这个过程继续进行下去，由于n为有限数，而每进行一步ia就要变小一次，于是，经过有限次后，比如m次，n就变为素数的乘积12mnp pp下面证明分解式是唯一的假设n还有另一个分解式12tnq qq，则有1212mtp ppq qq因为等式的右边能被1q整除，所以左边也能被1q整除，于是1q整除12,mppp中的某一个ip，但ip为素数，所以ip与1q相等，不妨设ip为1p，有11pq把等式两边约去11pq，得2323mtp ppq qq再重复上述步骤，又可得22pq，33pq，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比

23、如右边没有被约完（mt），则有121mmtqqq但12,mmtqqq均为素数，素数都大于1，有121mmtqqq，这表明等式不可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的将分解式按ip的递增排列，并将相同的ip合并成指数形式，即得1212kknppp其中12kppp为素数，12,k为正整数证明 2 用第二数学归纳法证明12mnp pp，12mppp（1）当2n，因为 2 为素数，命题成立13（2）假设命题对一切大于1 而小于n的正整数已成立这时，若n为素数，命题成立；若n不为素数，必存在,a b，使nab，1,1anbn，由归纳假设，小于n的,a b可分解为素数的乘积/1212/

24、1212,sssstsstap pppppbpppppp得/1212ssstnp pp qqq，适当调整/ip的顺序，可得命题对于正整数n成立由数学归纳法，命题对一切大于1 的正整数n成立下面证明分解式是唯一的假设n的分解式不唯一，则至少有两个分解式12mnp pp，12mppp，12tnq qq，12tqqq，得1212mtp ppq qq有112|tpq qq且112|mqp pp，这就存在,ijqp，使1|ipq且1|jqp，但11,ijp q qp均为为素数，所以11,ijpq qp，又111ijpqqpp，所以11pq把等式两边约去11pq，得2323mtp ppq qq再重复上述步

25、骤，又可得22pq，33pq，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（mt），则有121mmtqqq14 但12,mmtqqq均为素数，素数都大于1，有121mmtqqq，这表明上述等式不可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的将分解式按ip的递增排列，并将相同的ip合并成指数形式，即得1212kknppp其中12kppp为素数，12,k为正整数定理13若正整数n的素数分解式为1212kknppp则n的正约数的个数为12111kd naaa，n的一切正约数之和为121111212111111kkkpppS nppp证明对于正整数12

26、12kknppp，它的任意一个正约数可以表示为1212kkmppp，0ii，由于i有0,1,2,i共1i种取值，据乘法原理得n的约数的个数为12111kd naaa考虑乘积12010101111222kkkkppppppppp，展开式的每一项都是n的某一个约数（参见），反之，n的每一个约数都是展开式的某一项，于是，n的一切约数之和为110101111kkkS npppppp121111212111111kkkpppppp注构造法定义 8（高斯函数）对任意实数x，x是不超过x的最大整数亦称x为x的整数部分，1xxx定理 14在正整数!n的素因子分解式中，素数p作为因子出现的次数是23nnnppp

27、15 证明由于p为素数，故在!n中p的次方数是1,2,n各数中p的次方数的总和（注意，若p不为素数，这句话不成立）在1,2,n中，有np个p的倍数；在np个p的倍数的因式中，有2np个2p的倍数；在2np个2p的倍数的因式中，有3np个3p的倍数；，如此下去，在正整数!n的素因子分解式中，素数p作为因子出现的次数就为23nnnppp注省略号其实是有限项之和画线示意50!中 2 的指数 35678912450!2 3 5 7 11 13 17 1923 29 31 37 41 43 47定理 15（费玛小定理）如果素数p不能整除整数a，则11pp a证明 1 考察下面的1p个等式：11apqr，

28、10rp，222apqr，20rp111pppapqr，10prp由于素数p不能整除整数a，所以，p不能整除每个等式的左边，得121,pr rr均不为 0，只能取1,2,1p下面证明121,pr rr各不相等若不然，存在,11t stsp，使,ssttstsapqrtapqrrr相减stst ap qq应有素数p整除st a，但素数p不能整除a，所以素数p整除st，然而由11tsp可得16 02stpp，要素数p整除st是不可能的，得121,pr rr各不相等有1 211 211!prrrpp再把上述1p个等式相乘，有11 211!pppaMprrr，即11!1!ppaMpp，其中M是一个整数

29、亦即11!1ppaMp由于p是素数，不能整除1!p，所以素数p整除11pa，得证11pp a证明 2改证等价命题：如果素数p不能整除整数a，则modpaap只需对1,2,1ap证明成立，用数学归纳法（1）1a，命题显然成立（2）假 设 命 题 对11akkp成 立，则 当1ak时，由 于|1,2,1ipp Cip，故有11111ppppppkkC kCk11 modpkkp（用了归纳假设）这表明，命题对1ak是成立由数学归纳法得modpaap又素数p不能整除整数a，有,1a p，得11ppa定义 9 （欧拉函数）用n表示不大于n且与n互素的正整数个数定理 16设正整数1212kknppp，则1

30、2111111knnppp17 证明用容斥原理设1,2,Sn，记iA为S中能被ip整除的数所组成的集合（1,2,ik），用iA表示iA中元素的个数，有iinAp，1212,ijkijknnAAAAAp pp pp易知，1,2,Sn中与n互素的正整数个数为12kAAA，由容斥原理得12111211kiijikij kkijmkijm kAAASAAAAAAAAA1111211112121111111111111.kikijkijm kiijijmkki kij kijm kiijijmkknnnnnpp pp p pp ppnpp pp p pp ppnppp注 示意3n的容斥原理推论对素数p有

31、11,ppppp定理17整系数不定方程axbyc（0ab）存在整数解的充分必要条件是,a b c证明记,da b（1）必要性（方程有解必须满足的条件）若方程存在整数解，记为00,xxyy，则00axbyc，由|,|d a d b，有00|d axby，得证,|a bc（2）充分性（条件能使方程有解）若|d c，可设cde由于形如axby的数中有最小正数00axby满足18 00axby,a b两边乘以e，得00a exb eyc这表明方程有解00,.xexyey定理 18若0ab,1a b，且00,xxyy是整系数不定方程axbyc的一个整数解，则方程的一切整数解可以表示为00,xxbtyya

32、ttZ证明直接代入知是方程的整数解，下面证明任意一个整数解都有的形式.由00,xy是方程的一个解，有00axbyc，又方程的任意一个解,x y满足axbyc，相减000a xxb yy但,1a b，故有0|ayy，有00,xxyyt tZba得方程的任意一个整数解可以表示为00,xxbtyyattZ定义 10（平面整点）在平面直角坐标系上，纵横坐标都是整数的点称为整点（也称格点）类似地可以定义空间整点19 第二讲数论题的范例讲解主要讲几个重要类型：奇数与偶数，约数与倍数（素数与合数），平方数，整除，同余，不定方程，数论函数等 重点是通过典型范例来分析解题思路、提炼解题方法和巩固基本内容一、奇数

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

34、）奇数与偶数是相间排列的；两个连续整数中必是一个奇数一个偶数；（4）奇数个奇数的和是奇数；偶数个奇数的和是偶数；偶数跟奇数的和是奇数；任意多个偶数的和是偶数（5）除 2 外所有的正偶数均为合数；（6）相邻偶数的最大公约数为2，最小公倍数为它们乘积的一半（7）偶数乘以任何整数的积为偶数（8）两数和与两数差有相同的奇偶性，mod 2abab（9）乘积为奇数的充分必要条件是各个因数为奇数（10）n个偶数的积是2n的倍数（11）11k的充分必要条件是k为偶数，11k的充分必要条件是k为奇数（12）22220 mod4,211 mod4,211 mod8nnn（13）任何整数都可以表示为221mnk例

35、1（1906，匈牙利）假设12,na aa是1,2,n的某种排列，证明：如果n是奇数，则乘积1212naaan是偶数解法 1（反证法）假设1212naaan为奇数，则iai均为奇数，奇20 数个奇数的和还是奇数奇数=1212naaan12120naaan，这与“奇数偶数”矛盾所以1212naaan是偶数评析这个解法说明1212naaan不为偶数是不行的，但没有指出为偶数的真正原因体现了整体处理的优点，但掩盖了“乘积”为偶数的实质解法 2（反证法）假设1212naaan为奇数，则iai均为奇数，ia与i的奇偶性相反，1,2,n中奇数与偶数一样多，n为偶数但已知条件n为奇数，矛盾所以1212naa

36、an是偶数评析这个解法揭示了1212naaan为偶数的原因是“n为奇数”那么为什么“n为奇数”时“乘积”就为偶数呢？解法 3 121,2,nn a aa中有1n个奇数，放到n个括号，必有两个奇数在同一个括号，这两个奇数的差为偶数，得1212naaan为偶数评析这个解法揭示了1212naaan为偶数的原因是“当n为奇数时，1,2,n中奇数与偶数个数不等，奇数多，某个括号必是两个奇数的差，为偶数”类似题：例 1-1（1986，英国）设127,a aa是整数，127,b bb是它们的一个排列，证明112277ababab是偶数（127,a aa中奇数与偶数个数不等）例 1-2的前 24 位数字为3.

37、14159265358979323846264，记122 4,a aa为该 24 个数字的任一排列，求证12342324aaaaaa必为偶数（暗藏3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4中奇数与偶数个数不等）例 2能否从1,2,15中选出10个数填入图的圆圈中，使得每两个有线相连的圈中的数相减（大数减小数），所得的14 个差恰好为1,2,14？21 解考虑 14 个差的和S，一方面1214105S为奇数另一方面，每两个数,a b的差与其和有相同的奇偶性(mod2)abab，因此，14 个差的和S的奇偶性与14 个相应数之和的和/S的奇偶性相

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

39、 堆是可以保证因为苹果和梨数的奇偶性有且只有上述4 种可能，当把这些苹果和梨分成5 堆时，必有2 堆属于同一奇偶性，其和苹果数与梨数都是偶数例4有n个 数121,nnx xxx，它 们 中 的 每 一 个 要 么 是1，要 么 是1 若1223110nnnx xx xxxx x，求证4|n证明由1,1ix，有11,1iixx，再由1223110nnnx xx xxxx x，知n个1iix x中有一半是1，有一半是1，n必为偶数，设2nk现把n个1iix x相乘，有2222122311121(1)(1)1kknnnnnx xx xxxx xx xxx，可见，k为偶数，设2km，有4nm，得证4|

40、n例 5 n个整数121,nna aaa，其积为n，其和为0，试证4|n证明先证n为偶数，若不然，由121nna aaan知，121,nna aaa全为奇数，其和必为奇数，与其和为0（偶数），故n必为偶数（121,nna aaa中至少有1 个偶数）再证n为 4 的倍数，若不然，由n为偶数知，121,nna aaa恰有一个为偶数，其余1n个 数 全 为 奇 数，奇数 个奇 数 之 和 必 为 奇 数，加上 一 个 偶 数，总 和为 奇数，与121,nna aaa之和为 0 矛盾，所以，n为 4 的倍数，4|n（121,nna aaa中至少有22 2 个偶数）评析要证4|n，只须证121,nna

41、aaa中至少有2 个偶数，分两步，第一步证至少有 1 个偶数，第二步证至少有2个偶数例 6 在数轴上给定两点1 和2，在区间(1,2)内任取n个点，在此2n个点中，每相邻两点连一线段，可得1n条互不重叠的线段，证明在此1n条线段中，以一个有理点和一个无理点为端点的线段恰有奇数条证明将2n个点按从小到大的顺序记为122,nAAA，并在每一点赋予数值ia，使 1,1,iiiAaA当为有理数点时，当为无理数点时.与此同时，每条线段1iiA A也可数字化为1iia a（乘法）1111,1,iiiiiiA Aa aA A当一为有理数点，另一为无理数时，当同为有理数点或无理数点时,记11iiaa的线段有k

42、条，一方面112233412()()()()(1)(1)(1)kn kknna aa aa aaa另一方面12233412()()()()nna aa aa aaa21231212()1nnna a aaaa a，得11k，故k为奇数评析用了数字化、奇偶分析的技巧二、约数与倍数最大公约数与最小公倍数的求法（1）短除法（2）分解质因数法设1212,0,1,2,kkiapppik，1212,0,1,2,kkibpppik记min,max,iiiiii，则1212,kka bppp，1212,kka bppp23（3）辗转相除法121,0nnnna bb rr rrrrr例 7（1）求8381,10

43、15，8381,1015；（2）144,180,108，144,180,108解（1）方法 1 分解质因数法由283811729,101557 29,得8381,101529，28381,10155 7 1729293335方法 2 辗转相除法8838110153812078312612328232232290或232142213138232261101583812322327838120029232261qqqqrrrr或8381,1015261,1015261,23229,23229,0298381 10158381 10158381,10158381352933358381,101529

44、（2）方法 1 短除法由2 144 180 1082 72 90 543 36 30 27312 10 94 5 3得22144,180,1082336，43144,180,1082352160方法 2 分解质因数法由24 42222314423,180235,10823,，得22144,180,1082336，43144,180,1082352160例 8正整数n分别除以2,3,4,5,6,7,8,9,10得到的余数依次为1,2,3,4,5,6,7,8,9，则n的最小值为解 依题意，对最小的n，则1n是2,3,4,5,6,7,8,9,10的公倍数321235 7n，得2519n例 9 有两个

45、容器，一个容量为27 升，一个容量为15 升，如何利用它们从一桶油中倒出 6 升油来？解相当于求不定方程15276xy的整数解由15,273知，存在整数,u v，使15273uv，可得一个解2,1uv，从而方程1542726即往小容器里倒2 次油，每次倒满之后就向大容器里倒，大容器倒满时，小容器里剩有3 升油；再重复一次，可得6 升例10 对 每 一 个2n，求 证 存 在n个 互 不 相 同 的 正 整 数12,na aa，使ijijaaaa，对任意的,1,2,i jnij成立证明用数学归纳法当2n时，取121,2aa，命题显然成立假 设nk时，命 题 成 立，即 存 在12,ka aa，使

46、ijijaa aa，对 任 意 的,1,2,i jkij成立现取b为12,ka aa及它们每两个数之差的最小公倍数，则1k个数12,kb ab abab25 满足,ttijijabb abbabababab即命题对1nk时成立由数学归纳法知命题对2n成立例 11 1 11959,IMO证明对任意正整数n，分数214143nn不可约证明 1（反证法）假若214143nn可约，则存在1d，使214,143nnd，从而存在,1p qp q，使214,143,ndpndq消去n，3322，得132dqp，的1d由（1）、（5）矛盾，得1d解题分析：（1）去掉反证法的假设与矛盾就是一个正面证法（2）式是

47、实质性的进展，表明13 1432 214nn，可见214,1431nn由此获得2 个解法证明 2设214,143nnd存在,1p qp q，使214,143,ndpndq消去n，3-2，得132dqp得1d证明 3 由13 1432 214nn得214,1431nn证明 4 214,143nn26 71,143nn71,1n1解题分析：第相当于-；第相当于-2（-）=3-2；所以式与式的效果是一样的例 12 不存在这样的多项式1110mmmmf na nana na，使得对任意的正整数n，f n都是素数证明假设存在这样的多项式,对任意的正整数n，fn都是素数，则取正整数nb，有素数p使1110

48、mmmmf ba bababap，进而对任意的整数,k有1110mmmmf bkpabkpabkpabkpa1110mmmma baba baMp（二项式定理展开）1PM，其中M为整数，这表明f bkp为合数这一矛盾说明，不存在这样的多项式,对任意的正整数n，fn都是素数三、平方数若a是整数，则2a就叫做a的完全平方数，简称平方数1平方数的简单性质（1）平方数的个位数只有6 个：0,1,4,5.6.9（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）2220 mod4,21

49、1 mod4nn（）2211 mod 8n（6）凡是不能被3 整除的数，平方后被3 除余 1（7）在两个相邻整数的平方数之间，不能再有平方数（8）非零平方数的约数有奇数个27（9）直角三角形的三边均为整数时，我们把满足222abc的整数,a b c叫做勾股数勾股数的公式为2222,2,amnbmncmn其中,m n为正整数，,1m n且,m n一奇一偶这个公式可给出全部素勾股数2平方数的证明方法（1）反证法（2）恒等变形法（3）分解法设a为平方数，且abc，,1b c，则,b c均为平方数（4）约数法证明该数有奇数个约数3非平方数的判别方法（1）若221nxn，则x不是平方数（2）约数有偶数个

50、的数不是平方数（3）个位数为2，3，7，8 的数不是平方数（4）同余法：满足下式的数n都不是平方数2 mod3n，23 mod4n或，23 mod5n或，23567 mod8n或 或 或 或，2378 mod10n或 或 或（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 个学生，第一