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

《数学竞赛中的数论问题(20220320111507)》由会员分享，可在线阅读，更多相关《数学竞赛中的数论问题(20220320111507)（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 个学生，第一

51、个学生走过来，把凡是号码为1 的倍数的电灯的开关拉了一下；接着第 2个学生走过来，把凡是号码为2 的倍数的电灯的开关拉了一下；第 3 个学生走过来，把凡是号码为3 的倍数的电灯的开关拉了一下，如此等等，最后那个学生走过来，把编号能被100 整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的？讲解（1）直接统计100 次拉线记录，会眼花缭乱（2）拉电灯的开关有什么规律：电灯编号包含的正约数（学生）才能拉、不是正约数（学生）不能拉，有几个正约数就被拉几次28（3）灯被拉的次数与亮不亮（开、关）有什么关系：0 1 2 3 4 5 6 7 8 9 关开关开关开关开关开灯被拉奇数次的亮！（4）哪些数

52、有奇数个约数：平方数（5）1 100 中有哪些平方数：共10 个：1，4，9，16，25，36，49，64，81，100答案：编号为1，4，9，16，25，36，49，64，81，100 共 10 个灯还亮例 14已知直角三角形的两条直角边分别为正整数,a b，斜边为正整数c，若a为素数，求证21ab为平方数证明由勾股定理222cab，有2cbcba，但a为素数，必有2,1,cbacb解得2112ba，从而22212121abaaa，为平方数例 15 求证，任意3 个连续正整数的积不是平方数证明设存在3 个连续正整数1,1nn n（1n）的积为平方数，即存在整数m，使211nn nm，即221

53、nnm，但21,1nn，故21,nn均为平方数，有2221,nanbmab得222211211nannn，（注意1n）这一矛盾说明，3 个连续正整数的积不是平方数29 例 16 23 11986,IMO设d是异于 2，5，13 的任一整数求证在集合2,5,13,d中可以找到两个不同元素,a b，使得1ab不是完全平方数证明因为2222513,21315,5 1318，所以不是完全平方数只能是21,51,131ddd若结论不成立，则存在正整数,x y z，使22221,51,131,dxdydz同时成立，由知x是奇数，设21xn代入得2221dnn为奇数，代入、知,y z均为偶数设2,2yp z

54、q，代入、后相减，有222dqpqpqp由于2d为偶数，故,p q同奇偶，qpqp可被 4 整除，得d为偶数 这与上证d为奇数矛盾所以，在集合2,5,13,d中可以找到两个不同元素,a b，使得1ab不是完全平方数例 17 (29 6IMO)设,a b为正整数，1ab整除22ab证明221abab是完全平方数证明令221abkab，k是正整数式中,a b是对称的，不妨设ab(l)若ab，则2222211akk akka本题获证(2)若ab，由带余除法定理，可设abst（2,0,stb s t是整数)，则2222222211abb sbsttbabb sbt为正整数，由22222211b sbs

55、ttbsb sbt30 2222222222222221111110,1b sbsttbb sbstsb sbtb sbtbsttbsb sbtb s bts b btb bttb sbt且22222211b sbsttbsb sbt2222222222222222221211111110,1b sbstsb sbtb sbsttbb sbtbstsb sbttbb sbtbstbttsb sbb sbtt b stb bttb sbt得222222111b sbsttbssb sbt，所以必有2222221b sbsttbsb sbt，化简22btsbts，得221btsbt，于是22221

56、1abbtsabbt，其中tba此时若0t，则2kb，本题获证若0t，可继续令11btst（11112,0,stt s t是整数），仿上可推得222222111111ttabbtsabbttt，此时若10t，则2kt，本题获证31 若10t，可如上法做下去因120ttt，且均为整数故总能得到某个10it，使2ikt，是完全平方数综上本题获证这种证明的方法叫“无穷递降法”，是 17 世纪法国数学家费马(Fermat 1601 一 1665)首创和应用的一种方法四整除整除的判别方法主要有7 大类1定义法证b aabq，有三种方式（1）假设aqbr，然后证明0r（定理 4）（2）具体找出q，满足ab

57、q（3）论证q的存在例 18任意一个正整数m与它的十进制表示中的所有数码之差能被9 整除证明设1110101010nnnnmaaaa，其中09,0inaa，则110111121111101101101911111111,nnnnnnnnnnmaaaaaaaaaaa个个按定义1109nnmaaaa2数的整除判别法（1）任何整数都能被1 整除（2）如果一个整数的末位能被2 或整除，那么这个数就能被2 或整除（3）如果一个整数的末两位能被或25 整除，那么这个数就能被4 或 25 整除（4）如果一个整数的末三位能被8 或 125 整除，那么这个数就能被8 或 125 整除（5）如果一个整数各数位上的

58、数字之和能被3 或 9 整除，那么这个数就能被3 或 9 整除证明由101 mod3,101 mod9，有1110110101010mod3nnnnnnaaaaaaaa，1110110101010mod9nnnnnnaaaaaaaa（6）如果一个整数的末三位数与末三位数以前的数字所组成的数的差能被7 或 11 或 13整除，那么这个数就能被7 或 11 或 13 整除证明由1210nnma aa a a13132101001nnnna aaa aaa a a，32 知132101321010011001nnnna aa a a aa aaa a a，又由10017 11 13，而7,11,13

59、均为素数知，m能被 7 或 11 或 13 整除（7）如果一个整数的奇位数字之和与偶位数字之和的差能被11 整除，则这个数能被11 整除证明由101 mod11，有11101110101010111mod11.nnnnnnnnaaaaaaaa3分解法主要用乘法公式如123221nnnnnnnababaabababb212122232422322nnnnnnnababaabababb2221222322221nnnnnnnababaabababb例 19 试证555129129证明改证55545 129设555129S，则5555555555123441234182736459182736459

60、99,Smmmmmmmm得9 S又555555555192837465S51234412341928374655 22225,mmmmmmmm得5 S但9,51，得45 S，即555129129例 2021 11979,IMO设p与q为正整数，满足111112313181319pq，33 求证p可被 1979 整除（1979p）证明11111231 3 1 81 3 1 9pq1111111122313181319241318111111111231318131923659111166066113181319660 1319661 1318989990660 1319661 1318989 9

61、9019796606611319659!19791319!MM得 1979 整除1319!p，但 1979 为素数，1979,1319!1，得p可被 1979 整除例 20-1 2009 年 9 月 9日的年、月、日组成“长长久久、永不分离”的吉祥数字20090909，而它也恰好是一个不能再分解的素数若规定含素因子20090909的数为吉祥数，请证明最简分数111220090908mn的分子m是吉祥数证明：由111220090908mn11111112009090822009090710045454100454552009090920090909200909091 20090908220090

62、90710045454 1004545520090909,1 220090907 20090908p其中p为正整数，有200909091 22009090720090908npm，这表明，20090909整除1 220090907 20090908 m，但20090909为素数，不能整除1 220090907 20090908，所以20090909整除m，得m是吉祥数4 余数分类法例 21 试证3121n nn证明 1 任何整数n被 3 除其余数分为3 类34 3,31,32,nk nknkkZ，（1）3nk时，有12133161,n nnkkk有3121n nn（2）31nk时，有1 213

63、313221,n nnkkk有3121n nn（3）32nk1 21332165,n nnkkk有3121n nn综上得，3121n nn证明 2 222211214nnnn nn，得3 22221nnn，又3,41，得3121n nn5数学归纳法6反证法7构造法例 22 k个连续整数中必有一个能被k整除证明设k个连续整数为,1,2,1a aaak，若这k个数被k除没有一个余数为0，则这k个数的余数只能取1,2,1k，共1k种情况，必存在两个数,0ai ajijk，使1,aikqr2,ajkqr35 其中12qq，相减12ijk qq，有12ijk qqk，即ijk与ijk矛盾故k个连续整数中

64、必有一个能被k整除也可以由12ijk qq得120ijk qqk，推出1201qq，与12qq为整数矛盾例 23 k个连续整数之积必能被!k整除证明设k个连续整数为,1,2,1n nnnk，（1）若这k个连续整数为正整数，则121!n nnnknkknkknC只须证明，对任何一个素数p，分子中所含p的方次不低于分母中所含p的方次，由高斯函数的性质xyxy，有ssssknknknkpppp得knC为整数（证实了组合数的实际意义）（2）若这k个连续整数中有0，则连乘积为0，必能被!k整除（3）若这k个连续整数为负整数，则121!1211!1,kkknn nnnkknnnnkkC由（1）知knC为整

65、数，故121!n nnnkk为整数例 24 有男孩、女孩共n个围坐在一个圆周上（3n），若顺序相邻的3 人中恰有一36 个男孩的有a组，顺序相邻的3 人中恰有一个女孩的有b组，求证3 ab证明现将小孩记作(1,2,)ia in，且数字化1,1,iiiaaa表示男孩时表示女孩时则“3 人组”数值化为12121212123,3,1,1,iiiiiiiiiiiiiiiia aaa aaAaaaa aaa aa 均为男孩均为女孩 恰有一个女孩恰有一个男孩其中njjaa又设取值为3 的iA有p个，取值为3的iA有q个，依题意，取值为1 的iA有b个，取值为1的iA有a个，得1212323413()()(

66、)()nnaaaaaaaaaaaa3(3)(1)3()()pqabpqba，可见3 ab例 25（1956，中国北京）证明3231122nnn对任何正整数n都是整数，并且用3除时余 2分析只需说明23131222nnnn为整数，但不便说明“用3 除时余 2”，应说明3212131222n nnnnn是 3 的倍数作变形32222213111,3,81228nnnnnn，命题可证证明已知即321213111222n nnnnn，因为相邻2 个整数,1n n必有偶数，所以3231122nnn为整数又可变为37 32222213111228nnnnnn，因为相邻3 个整数2,22,21nnn必有 3 的倍数，故22221nnn能被 3整除；又3,81，所以222218nnn能被 3 整除；得3231122nnn用 3 除时余 2五、同余根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解题例 26 正方体的顶点标上1或1，面上标上一个数，它等于这个面四个顶点处的数的乘积，求证，这样得出的14 个数之和不能为0证明记 14 个数的和为S，易知，这 14 个数不是