数学竞赛中的数论问题

数学竞赛中的数论问题 罗增儒

引言

数论的认识：数论是关于数的学问，主要研究整数，重点对象是正整数，对中学生可以说，数论是研究正整数的一个数学分支．

什么是正整数呢？人们借助于“集合”和“后继”关系给正整数（当时也即自然数）作过本质的描述，正整数1，2，3，?是这样一个集合N?：

（1）有一个最小的数1．

（2）每一个数a的后面都有且只有一个后继数a；除1之外，每一个数的都是且只是一个数的后继数．

这个结构很像数学归纳法，事实上，有这样的归纳公理：

（3）对N?的子集M，若1?M，且当a?M时，有后继数a?M，则M?N?． 就是这么一个简单的数集，里面却有无穷无尽的奥秘，有的奥秘甚至使得人们怀疑：人类的智慧还没有成熟到解决它的程度．比如，哥德巴赫猜想：

1742年6月7日，普鲁士派往俄国的一位公使哥德巴赫写信给欧拉，提出“任何偶数，由4开始，都可以表示为两个素数和的形式，任何奇数，由7开始，都可以表示为三个素数的和．后者是前者的推论，也可独立证明（已解决）．“表示为两个素数和的形式”就是著名的哥德巴赫猜想，简称1+1．

欧拉认为这是对的，但证不出来．

1900年希尔伯特将其归入23个问题中的第8个问题． 1966年陈景润证得：一个素数+素数?素数（1+2），至今仍无人超越． ●陈景润的数学教师沈元很重视利用名人、名言、名事去激励学生，他曾多次在开讲时，说过这样的话:“自然科学的皇后是数学，数学的皇冠是数论，哥德巴赫猜想则是皇冠上的明珠．??”陈景润就是由此而受到了启示和激励，展开了艰苦卓绝的终生奋斗和灿烂辉煌的奋斗终生，离摘取“皇冠上的明珠”仅一步之遥．

●数论题涉及的知识不是很多，但用不多的知识来解决问题往往就需要较强的能力和精明多的技巧，有人说：用以发现数学人才，在初等数学中再也没有比数论教材更好的课程了．任何学生如能把当今一本数论教材中的练习做出，就应当受到鼓励，劝他（她）将来去从事数学方面的工作（U．Dudley《数论基础》前言）．下面，是一个有趣的故事．

当代最高产的数学家厄尔多斯听说一个叫波萨（匈牙利，1948）的小男孩很聪明，就问了他一个问题加以考察（1959）：如果你手头上有n?1个正整数，这些正整数小于或等于2n，那么你一定有一对整数是互素的，你知道这是什么原因吗？

不到12岁的波萨只用了1分半钟，就给出了问题的解答．他将1～2n分成（1，2），（3，4），?，（2n?1,2n）共n个抽屉，手头的n?1个正整数一定有两个属于同一抽屉，这两个数是相邻的正整数，必定互素．

通过这个问题，厄尔多斯认定波萨是个难得的英才，就精心加以培养，不到两年，14岁的波萨就发表了图论中“波萨定理”．

●重视数学能力的数学竞赛，已经广泛采用数论题目，是数学竞赛四大支柱之一，四大

// 1

支柱是：代数，几何，初等数论，组合初步（俗称代数题、几何题、算术题和智力题）．高中竞赛加试四道题正好是四大模块各一题，分别是几何题、代数题、数论题、组合题，一试中也会有数论题．数论受到数学竞赛的青睐可能还有一个技术上的原因，就是它能方便地提供从小学到大学各个层面的、新鲜而有趣的题目．

数论题的主要类型：在初中竞赛大纲中，数论的内容列有：十进制整数及表示方法；整除性，被2、3、4、5、8、9、11等数整除的判定；素数和合数，最大公约数与最小公倍数；奇数和偶数，奇偶性分析；带余除法和利用余数分类；完全平方数；因数分解的表示法，约数个数的计算； 简单的一次不定方程．

在高中竞赛大纲中，数论的内容列有：同余，欧几里得除法，裴蜀定理，完全剩余类，二次剩余，不定方程和方程组，高斯函数[x]，费马小定理，格点及其性质，无穷递降法，欧拉定理?，孙子定理?．

根据已出现的试题统计，中学数学竞赛中的数论问题的主要有8个重点类型： （1）奇数与偶数（奇偶分析法、01法）； （2）约数与倍数、素数与合数； （3）平方数； （4）整除； （5）同余； （6）不定方程；

（7）数论函数、?x?高斯函数、??n?欧拉函数；

（8）进位制（十进制、二进制）．

下面，我们首先介绍数论题的基本内容（10个定义、18条定理），然后，对数学竞赛中的数论问题作分类讲解．

2

第一讲 数论题的基本内容

中学数学竞赛中的数论问题涉及的数论内容主要有10个定义、18条定理． 首先约定，本文中的字母均表示整数．

定义1 （带余除法）给定整数a,b,b?0,如果有整数q,r0?r?b满足 a?qb?r，

则q和r分别称为a除以b的商和余数．特别的，r?0时，则称a被b整除，记作ba，或者说a是b的倍数，而b是a的约数．（q,r的存在性由定理1证明）

定义2 （最大公约数）设整数a1,a2,?,an中至少有一个不等于零，这n个数的最大公约数是能整除其中每一个整数的最大正整数，记作?a1,a2,?,an?．

?a1,a2,?,an?中的ai没有顺序，最大公约数也称最大公因数． 简单性质：?a1,a2,?,an??a1,a2,?,an．

一个功能：可以把对整数的研究转化为对非负整数的研究．

定义3 （最小公倍数）非零整数a1,a2,?,an的最小公倍数是能被其中每一个

????ai?1?i?n?所整除的最小正整数，记作?a1,a2,?,an?．

简单性质：如果k是正整数a,b的公倍数，则存在正整数m使k?m?a,b?

证明 若不然，有k?m?a,b??r（0?r??a,b?），由k,?a,b?都是a,b的公倍数得r也是a,b的公倍数，但0?r??a,b?，与?a,b?的最小性矛盾．故k?m?a,b?．

定义4 如果整数a,b 满足?a,b??1，则称a与b是互素的（也称互质）．

定义5 大于1且除1及其自身外没有别的正整数因子的正整数，称为素数（也称质数）．其余大于1的正整数称为合数；数1既不是素数也不是合数．

定理1 若a,b是两个整数，b?0，则存在两个实数q,r，使a?qb?r?0?r?b?，并且q,r是唯一性．

证明1 先证存在性．作序列

?,?3b.?2b,?b,0,b,2b,3b,?

则a必在上述序列的某两项之间，从而存在一个整数q，使

qb?a??q?1?b，

3

即 0?a?qb?b， 取 r?a?qb， 0?r?b， 得 a?qb?r，

即存在两个实数q,r，使a?qb?r?0?r?b?． 再证唯一性．假设不唯一，则同时存在q1,r1与q1,r2，使 a?q1b?r1?0?r1?b?， a?q2b?r2?0?r2?b?， 相减 ?q1?q2?b?r2?r1， q1?q2b?r2?r1?b， 0?q1?q2?1，

但q1?q2为整数，故q1?q2?0，得q1?q2，从而r1?r2．

注：如果取消0?r?b，当r?0或r?b，不保证唯一． 经典方法：紧扣定义，构造法证存在性，反证法证唯一性． 证明2 只证存在性，用高斯记号，由 0?ab???a??b???1， 有 0?a?b??a??b???b，

记r?a?b??a??，故存在q???a??a??b??b??,r?a?b??b??,0?r?b使

a?qb?r?0?r?b?．

证明3 只证存在性，作集合

M??a?bx|x?Z,a?bx?0?

这是一个有下界的非空整数集，其中必有最小的，设x?q时，有最小值r?r?0? a?qb?r．

再证r?b，若不然，r?b，记r?b?r1，有

4

a?qb?r?qb??b?r1??b?q?1??r1

r1?a?b?q?1??M

即M有r1比r更小，这与r为最小值矛盾． 故存在两个实数q,r，使a?qb?r?0?r?b?．

定理2 设a,b,c是三个不全为0的整数，满足a?qb?c，其中q也为整数，则

?a,b???b,c?．

证明 设A?｛a,b的公约数｝， B?｛b,c的公约数｝．

任取d?A???d|a?d|c?a?bq???d?B?A?B， d|bd|b???d|b?d|b???d?A?B?A， 任取d?B??d|cd|a?bq?c??得 A?B．

有A中元素的最大值?B中元素的最大值，即

?a,b???b,c?．

注：这是辗转相除法求最大公约数的理论基础．

经典方法：要证明A?B，只需证A?B且B?A． 定理3 对任意的正整数a,b，有 ?a,b???a,b??ab．

证明 因为ab是a,b的公倍数，所以a,b的最小公倍数也是ab的约数，存在q使 ab?q?a,b?，

有

a,b??a,b??a?q且为整数，

bb故q是a的约数．同理q是b的约数，即q是a,b的公约数．下面证明，q是a,b的最大公约数．若不然，q??a,b?．有

ab?q?a,b???a,b??a,b?． ①

5

设k?abbaba?a?b，可见k是a的倍数，同样k?，k是b的倍a,ba,ba,ba,b????????数，即k是a,b的公倍数，则存在正整数m使k?m?a,b?，有

ab?m?a,b???a,b?， ?a,b?得 ab?q?a,b???a,b??a,b?

与①矛盾，所以，q??a,b?，得证?a,b???a,b??ab．

ab?a,b??qk?注 也可以由1?m?，得q??a,b?，与q??a,b?矛盾．

ab?a,b??a,b?q两步ab?q?a,b?,ab??a,b?k可以交换吗？

定理4 a,b是两个不同时为0的整数，若ax0?by0是形如ax?by（x,y是任意整数）的数中的最小正数，则

（1）ax0?by0|ax?by； （2）ax0?by0??a,b?． 证明 （1）由带余除法有

ax?by??ax0?by0?q?r，0?r?ax0?by0， 得 r?a?x?qx0?x?b?y?qy0??ax0?by0，

知r也是形如ax?by的非负数，但ax0?by0是形如ax?by的数中的最小正数，故r?0，即

ax0?by0|ax?by．

（2）由（1）有

ax0?by0|a?1?b?0?a， ax0?by0|a?0?b?1?b，

得ax0?by0是a,b的公约数．另一方面，a,b的每一个公约数都可以整除ax0?by0，所以

ax0?by0是a,b的最大公约数，ax0?by0??a,b?．

6

推论 若?a,b??1，则存在整数s,t，使as?bt?1．（很有用） 定理5 互素的简单性质： （1）?1,a??1． （2）?n,n?1??1． （3）?2n?1,2n?1??1．

（4）若p是一个素数，a是任意一个整数，且a不能被p整除，则?a,p??1． 证明 因为?a,p?|p，所以，素数p的约数只有两种可能：?a,p??1,?a,p??p．但

a不能被p整除，?a,p??p，得?a,p??1．

推论 若p是一个素数，a是任意一个整数，则?a,p??1或?a,p??p． （5）若?a,b??1，则存在整数s,t，使as?bt?1．（定理4推论） （6）若?a,b??1,?a,c??1，则?a,bc??1． 证明 由?a,b??1知存在整数s,t，使as?bt?1． 有 a?cs??bct?c， 得 ?a,bc???a,c??1．

（7）若?a,b??1，则?a?b,a??1，?a?b,b??1， ?a?b,ab??1． 证明 ?a?b,a????b,a???b,a??1， ?a?b,b???a,b??1， 由（6）?a?b,ab??1． （8）若?a,b??1，则a,bm?n??1，其中m,n为正整数． ?m证明 据（6），由?a,b??1可得a,b?1． 同样，由a,b?1可得a,b??m??mn??1．

定理6 设a是大于1的整数，则a的除1之外的最小的正约数q必是素数，且当a是合数时，q?a．

7

1?q1?q，证明 用反证法，假设q不是素数，则存在正整数数q1，使q1|q，但q|a，

故有q1|a，这与q是a的除1之外的最小正约数矛盾，故q是素数．

当a是合数时，设a?a1q，则a1也是a的一个正约数，由q的最小性得q?a1，从而

q2?a1q?a，开方得q?a．

定理7 素数有无穷多个，2是唯一的偶素数．

证明 假设素数只有有限多个，记为p1,p2,?,pn，作一个新数

??pn?1?1． p?p1?p2?若p为素数，则与素数只有 n个p1,p2,?,pn矛盾．

若p为合数，则必有pi??p1,p2,?,pn?，使pi|p，从而pi|1，又与pi?1矛盾． 综上所述，素数不能只有有限多个，所以素数有无穷多个．

2是素数，而大于2的偶数都是合数，所以2是唯一的偶素数．

注：这个证明中，包含着数学归纳法的早期因素：若假设有n个素数，便有n?1个素数．（构造法、反证法）秒

定理8（整除的性质）整数a,b,c通常指非零整数 （1）1a，?1|a；当a?0时，a|a，a|0．

（2）若ba，a?0，则b?a;若ba，b?a，则a?0;若ab?0，且ba,ab，则a?b．

证明 由ba，a?0，有a?bq，得a?bq?b． 逆反命题成立“若ba，b?a，则a?0”; 由b?a且b?a得a?b，又ab?0，得a?b． （3）若a?b?c?d，且e|a,e|b,e|c，则e|d． （4）若cb，ba，则ca． 证明 （定义法）由cb，ba，有 b?q1c,a?q2b， 得 a??q1q2?c，

8

即 ca．

（5）若ca，则bcab．

（6）若ca，cb，则对任意整数m,n，有cma?nb． 证明 （定义法）由ca，cb，有 a?q1c,b?q2c， 得 ma?nb??mq1?nq2?c， 即 cma?nb．

（7）若?a,b??1，且abc，则ac．

证明 由?a,b??1知存在整数s,t，使as?bt?1，有

a?cs???bc?t?c，

因为aa，abc，所以a整除等式的左边，进而整除等式的右边，即ac．

注意 不能由abc且a?|b得出ac．如64?9，但6?|4且6?|9． （8）若?a,b??1，且ac,bc，则abc．

证明 由?a,b??1知存在整数s,t，使as?bt?1，有

acs?bct?c，

又由ac,bc有c?aq1,c?bq2代入得

ab?q2s??ab?q1t??c，

所以abc．

注意 不能由ac且bc得出abc．如不能由630且10|30得出60|30． （9）若a为素数，且abc，则ab或ac．

证明 若不然，则a?由a为素数得?a,b??1,?a,c??1，由互素的性质（6）|b且a?|c，得?a,bc??1，再由a为素数得a?|bc，与abc矛盾．

注意 没有a为素数，不能由abc推出ab或ac．如64?9，但6?|4且6?|9．

9

定义6 对于整数a,b,c，且c?0，若c(a?b)，则称a,b关于模c同余，记作

|?a?b?，则称a,b关于模c不同余，记作aa?b(modc)；若c?定理9（同余的性质）设a,b,c,d,m为整数，m?0, （1）若a?b(modm)且b?c(modm)，则a?c(modm)； 证明 由a?b(modm)且b?c(modm)，有 a?b?mq1,b?c?mq2，

b(modc)．

a?c?m?q1?q2?，

得a?c(modm)． （2）若a?bm(odm)且c?d(modm)，则a?c?b?dm(odm)且ac?bd(modm)．

证明 由a?b(modm)且c?d(modm)，有

a?b?mq1,c?d?mq2， ① 对①直接相加 ，有

?a?c???b?d??m?q1?q2?，

得 a?c?b?d(modm).

对①分别乘以c,b后相加，有

ac?bd??ac?bc???bc?bd??m?cq1?bq2?，

得 ac?bd(modm)．

（3）若a?b(modm)，则对任意的正整数n有a?b(modm)且an?bn(modmn).

nn（4）若a?b(modm)，且对非零整数k有k(a,b,m)，则

ab?m???mod?． kk?k?证明 由a?b(modm)、，有 a?b?mq， 又k(a,b,m)，有

abm,,均为整数，且 kkk10

abm??q， kkk得

ab?m???mod?． kk?k?定理10 设a,b为整数，n为正整数， （1）若a?b，则?a?b?a?bn?n?．

?b2n?1?．

an?bn??a?b??an?1?an?2b?an?3b2???abn?2?bn?1?．

（2）若a??b，则?a?b?a?2n?1a2n?1?b2n?1??a?b??a2n?2?a2n?3b?a2n?4b2???ab2n?3?b2n?2?．

（3）若a??b，则?a?b?a?2n?b2n?．

a2n?b2n??a?b??a2n?1?a2n?2b?a2n?3b2???ab2n?2?b2n?1?．

定义7 设n为正整数，k为大于2的正整数, a1,a2,?,am是小于k的非负整数，且

a1?0．若

n?a1km?1?a2km?2???am?1k?am，

则称数a1a2?am为n的k进制表示．

定理11 给定整数k?2，对任意的正整数n，都有唯一的k进制表示．如

n?a110m?1?a210m?2???am?110?am，0?ai?9,a1?0（10进制） n?a12m?1?a22m?2???am?12?am．0?ai?1,a1?0（２进制）

定理12 （算术基本定理）每个大于1的正整数都可分解为素数的乘积，而且不计因

数的顺序时，这种表示是唯一的

n?p11p22?pk???k，

其中p1?p2???pk为素数，?1,?2,?,?k为正整数． （分解唯一性） 证明1 先证明，正整数n可分解为素数的乘积

n?p1p2?pm． ①

如果大于1的正整数n为素数，命题已成立．

当正整数n为合数时，n的正约数中必有一个最小的，记为p1，则p1为素数，有

11

n?p1a1，1?a1?n．

如果a1为素数，命题已成立．当a1为合数时，a1的最小正约数p2为必为素数，有

n?p1a1?p1p2a2，1?a2?a1?n．

这个过程继续进行下去，由于n为有限数，而每进行一步ai就要变小一次，于是，经过有限次后，比如m次，n就变为素数的乘积

n?p1p2?pm．

下面证明分解式是唯一的．假设n还有另一个分解式

n?q1q2?qt， ② 则有 p1p2?pm?q1q2?qt． ③

因为等式的右边能被q1整除，所以左边也能被q1整除，于是q1整除p1,p2,?,pm中的某一个pi，但pi为素数，所以pi与q1相等，不妨设pi为p1，有

p1?q1．

把等式③两边约去p1?q1，得 p2p3?pm?q2q3?qt．

再重复上述步骤，又可得p2?q2，p3?q3，?，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（m?t），则有

1?qm?1qm?2?qt． ④

但qm?1,qm?2,?,qt均为素数，素数都大于1，有qm?1qm?2?qt?1，这表明等式④不可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的． 将分解式按pi的递增排列，并将相同的pi合并成指数形式，即得

n?p1?1p2?2?pk?k．

其中p1?p2???pk为素数，?1,?2,?,?k为正整数． 证明2 用第二数学归纳法证明

n?p1p2?pm，p1?p2???pm．

（1）当n?2，因为2为素数，命题成立．

12

（2）假设命题对一切大于1而小于n的正整数已成立． 这时，若n为素数，命题成立；若n不为素数，必存在a,b，使 n?ab，1?a?n,1?b?n， 由归纳假设，小于n的a,b可分解为素数的乘积

//a?p1/p2?ps/, p1/?p2???ps/,

b?p/s?1/p//s?2?p, p////t/s?1?p//s?2???p,/t

得 n?p1p2?psqs?1qs?2?qt，

适当调整pi的顺序，可得命题对于正整数n成立．

由数学归纳法，命题对一切大于1的正整数n成立．

下面证明分解式是唯一的．假设n的分解式不唯一，则至少有两个分解式

/n?p1p2?pm，p1?p2???pm，

n?q1q2?qt，q1?q2???qt， 得 p1p2?pm?q1q2?qt． 有 p1|q1q2?qt且q1|p1p2?pm， 这就存在qi,pj，使

p1|qi且q1|pj，

但p1,qi,q1,pj均为为素数，所以

p1?qi,q1?pj，

又 p1?qi?q1?pj?p1， 所以 p1?q1．

把等式两边约去p1?q1，得 p2p3?pm?q2q3?qt．

再重复上述步骤，又可得p2?q2，p3?q3，?，直到等式某一边的因数被全部约完，这时，如果另一边的因数没有约完，比如右边没有被约完（m?t），则有

1?qm?1qm?2?qt．

13

但qm?1,qm?2,?,qt均为素数，素数都大于1，有qm?1qm?2?qt?1，这表明上述等式不可能成立，两个分解式的因数必然被同时约完，即分解式是唯一的． 将分解式按pi的递增排列，并将相同的pi合并成指数形式，即得

n?p1?1p2?2?pk?k．

其中p1?p2???pk为素数，?1,?2,?,?k为正整数． 定理13 若正整数n的素数分解式为 n?p11p22?pk???k则n的正约数的个数为

d?n???a1?1??a2?1???ak?1?，

n的一切正约数之和为

pk?k?1?1p1?1?1?1p2?2?1?1???? S?n??．

p1?1p2?1pk?1证明 对于正整数n?p11p22?pk m?p11p22?pk???k???k，它的任意一个正约数可以表示为

，0??i??i ， ①

由于?i有0,1,2,?,?i共?i?1种取值，据乘法原理得n的约数的个数为

d?n???a1?1??a2?1???ak?1?．

考虑乘积

p1?p1???p1?01?1??p02?p21???p2?2??pk0?pk1???pk?k， ??展开式的每一项都是n的某一个约数（参见①），反之，n的每一个约数都是展开式

的某一项，于是，n的一切约数之和为

S?n???p10?p11???p1?1???pk0?pk1???pk?1?

pk?k?1?1p1?1?1?1p2?2?1?1?????．

p1?1p2?1pk?1注 构造法．

定义8 （高斯函数）对任意实数x，?x?是不超过x的最大整数．亦称?x?为x的整数部分，?x??x??x??1．

定理14 在正整数n!的素因子分解式中，素数p作为因子出现的次数是

?

?n??n??n???2???3???． ??p??p??p?14

证明 由于p为素数，故在n!中p的次方数是1,2,?,n各数中p的次方数的总和（注意，若p不为素数，这句话不成立）．

在1,2,?,n中，有??n??n??n?2个的倍数；在个的倍数的因式中，有个p的pp????2??p??p??p?倍数；在??n??n?23个的倍数的因式中，有个p的倍数；?，如此下去，在正整数n!p?2?3??p??p?的素因子分解式中，素数p作为因子出现的次数就为

??n??n??n????p2???p3???． p??????注 省略号其实是有限项之和．

画线示意50!中2的指数．

50!?2?13?25?37?411?513?617?719?823?929?31?37?41?43?47

定理15 （费玛小定理）如果素数p不能整除整数a，则pa证明1 考察下面的p?1个等式： a?pq1?r1，0?r1?p，

?p?1?1?．

2a?pq2?r2，0?r2?p

??

?p?1?a?pqp?1?rp?1，0?rp?1?p

由于素数p不能整除整数a，所以，p不能整除每个等式的左边，得r1,r2,?,rp?1均不为0，只能取1,2,?,p?1．下面证明r1,r2,?,rp?1各不相等．

若不然，存在t,s,1?t?s?p?1，使

sa?pqs?rs, ta?pqt?rt,

rs?rt,相减 ?s?t?a?p?qs?qt?．

应有素数p整除?s?t?a，但素数p不能整除a，所以素数p整除?s?t?，然而由

1?t?s?p?1可得

15

0?s?t?p?2?p，

要素数p整除?s?t?是不可能的，得r1,r2,?,rp?1各不相等．有

r1r2?rp?1?1?2????p?1???p?1?!．

再把上述p?1个等式相乘，有 ?p?1?!ap?1?Mp?r1r2?rp?1， 即 ?p?1?!ap?1?Mp??p?1?!， 其中M是一个整数．

亦即 ?p?1?!?ap?1?1??Mp．

由于p是素数，不能整除?p?1?!，所以素数p整除ap?1?1，得证

p?ap?1?1?

证明2 改证等价命题：如果素数p不能整除整数a，则ap?a?modp?． 只需对a?1,2,?,p?1证明成立，用数学归纳法． （1）a?1，命题显然成立．

（2）假设命题对a?k?1?k?p?1?成立，则当a?k?1时，p|Cip?i?1,2,?,p?1?，故有

?k?1?p?kp?C1p?1pk???Cp?1pk?1

?kp?1?k?1?modp?．（用了归纳假设）

这表明，命题对a?k?1是成立． 由数学归纳法得ap?a?modp?．

又素数p不能整除整数a，有?a,p??1，得p?ap?1?1?．

定义9 （欧拉函数）用??n?表示不大于n且与n互素的正整数个数． 定理16 设正整数n?p?11p??22?pkk，则

??n??n??1?1???p??1?1?????1?1??． 1??p2??pk? 于

16

由证明 用容斥原理．设S??1,2,?,n?，记Ai为S中能被pi整除的数所组成的集合（i?1,2?,k），用Ai表示Ai中元素的个数，有

Ai?nnn,?,A1?A2???Ak?，Ai?Aj?． pipjp1p2?pkpi易知，S??1,2,?,n?中与n互素的正整数个数为 A1?A2??Ak， 由容斥原理得

A1?A2??Ak?S?

1?i?k?Ai?1?i?j?kk?Ai?Aj

?1?i?j?m?k?Ai?Aj?Am?????1?A1?A2???Ak?n????1?i?k?nnnnk?????????1?pi1?i?j?kpipj1?i?j?m?kpipjpmp1p2?pk?1111k?????????1?? pi1?i?j?kpipj1?i?j?m?kpipjpmp1p2?pk?? ?n?1?1?i?k??1??1??1??n?1???1????1??.p1??p2??pk??注 示意n?3的容斥原理． 推论 对素数p有??p??p?1,?p???p???p??1．

定理17 整系数不定方程ax?by?c（ab?0）存在整数解的充分必要条件是

?a,b?c．

证明 记d??a,b?．

（1）必要性（方程有解必须满足的条件）．若方程存在整数解，记为??x?x0,，则

?y?y0,ax0?by0?c，

由d|a,d|b， 有d|ax0?by0，得证?a,b?|c．

（2）充分性（条件能使方程有解）．若d|c，可设c?de由于形如ax?by的数中有最小正数ax0?by0满足

17

ax0?by0??a,b?．

两边乘以e，得

a?ex0??b?ey0??c

?x?ex0,这表明方程有解?

y?ey.0?定理18 若ab?0,?a,b??1，且?解，则方程的一切整数解可以表示为

?x?x0,是整系数不定方程ax?by?c的一个整数

?y?y0,?x?x0?bt, ??t?Z?． ①

y?y?at,0?证明 直接代入知①是方程的整数解，下面证明任意一个整数解都有①的形式. 由?x0,y0?是方程的一个解，有

ax0?by0?c，

又方程的任意一个解?x,y?满足

ax?by?c， ② 相减 a?x?x0??b?y?y0??0． ③ 但?a,b??1，故有 a|?y?y0?， 有

x?x0y?y0??t,t?Z ?ba得方程的任意一个整数解可以表示为 ??x?x0?bt,?t?Z?．

?y?y0?at,定义10 （平面整点）在平面直角坐标系上，纵横坐标都是整数的点称为整点（也称格点）．类似地可以定义空间整点．

18

第二讲 数论题的范例讲解

主要讲几个重要类型：奇数与偶数，约数与倍数（素数与合数），平方数，整除，同余，不定方程，数论函数等．重点是通过典型范例来分析解题思路、提炼解题方法和巩固基本内容．

一、奇数与偶数

整数按照能否被2整除可以分为两类，一类余数为0，称为偶数，一类余数为1，称为奇数．偶数可以表示为2n，奇数可以表示为2n?1或2n?1．一般地，整数被正整数m去除，按照余数可以分为m类，称为模m的剩余类Ci?xx?i?modm?，从每类中各取出一个元素ai?Ci，可得模m的完全剩余系（剩余类派出的一个代表团），0,1,2,?,m?1称为模m的非负最小完全剩余系.

通过数字奇偶性质的分析而获得解题重大进展的技巧，常称作奇偶分析，这种技巧与分类、染色、数字化都有联系，在数学竞赛中有广泛的应用． 关于奇数和偶数，有下面的简单性质：

（1）奇数?偶数．

（2）偶数的个位上是0、2、4、6、8；奇数的个位上是1、3、5、7、9． （3）奇数与偶数是相间排列的；两个连续整数中必是一个奇数一个偶数；． （4）奇数个奇数的和是奇数；偶数个奇数的和是偶数；偶数跟奇数的和是奇数；任意多个偶数的和是偶数．

（5）除2外所有的正偶数均为合数；

（6）相邻偶数的最大公约数为2，最小公倍数为它们乘积的一半． （7）偶数乘以任何整数的积为偶数．

（8）两数和与两数差有相同的奇偶性，a?b?a?b?mod2?． （9）乘积为奇数的充分必要条件是各个因数为奇数． （10）n个偶数的积是2的倍数．

（11）??1??1的充分必要条件是k为偶数，??1???1的充分必要条件是k为奇数．

（12）?2n??0?mod4?,?2n?1??1?mod4?,?2n?1??1?mod8?． （13）任何整数都可以表示为n?2??

例1 （1906，匈牙利）假设a1,a2,?,an是1,2,?,n的某种排列，证明：如果n是奇数，则乘积

?a1?1??a2?2???an?n? 是偶数．

解法1 （反证法）假设?a1?1??a2?2???an?n?为奇数，则ai?i均为奇数，奇

19

m222kk??n?2k?1?．

数个奇数的和还是奇数

奇数=?a1?1???a2?2?????an?n?

??a1?a2???an???1?2???n??0，

这与“奇数?偶数”矛盾． 所以?a1?1??a2?2???an?n?是偶数．

评析 这个解法说明?a1?1??a2?2???an?n?不为偶数是不行的，但没有指出为偶数的真正原因．体现了整体处理的优点，但掩盖了“乘积”为偶数的实质．

解法2 （反证法）假设?a1?1??a2?2???an?n?为奇数，则ai?i均为奇数，ai与

i的奇偶性相反，?1,2,?,n?中奇数与偶数一样多，n为偶数．但已知条件n为奇数，矛

盾． 所以?a1?1??a2?2???an?n?是偶数．

评析 这个解法揭示了?a1?1??a2?2???an?n?为偶数的原因是“n为奇数”．那么为什么“n为奇数”时“乘积”就为偶数呢？

解法3 1,2,?,n,a1,a2,?,an中有n?1个奇数，放到n个括号，必有两个奇数在同一个括号，这两个奇数的差为偶数，得?a1?1??a2?2???an?n?为偶数．

评析 这个解法揭示了?a1?1??a2?2???an?n?为偶数的原因是“当n为奇数时，． 1,2,?,n中奇数与偶数个数不等，奇数多，某个括号必是两个奇数的差，为偶数”

类似题：

例1-1（1986，英国）设a1,a2,?,a7是整数，b1,b2,?,b7是它们的一个排列，证明

?a1?b1??a2?b2???a7?b7?是偶数．

（a1,a2,?,a7中奇数与偶数个数不等）

a2,?,a4 例1-2 ?的前24位数字为??3.14159265358979323846264，记a1,2该24个数字的任一排列，求证?a1?a2??a3?a4???a23?a24?必为偶数．

为

（暗藏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？

20

解 考虑14个差的和S，一方面

S?1?2???14?105为奇数．

另一方面，每两个数a,b的差与其和有相同的奇偶性 a?b?a?b(mod2)，因此，14个差的和S的奇偶性与14个相应数之和的和S的奇偶性相同，由于图中的每一个数a与2个或4个圈中的数相加，对S的贡献为2a或4a，从而S为偶数，这与S为奇数矛盾，所以不能按要求给图中的圆圈填数．

评析：用了计算两次的技巧．对同一数学对象，当用两种不同的方式将整体分为部分时，则按两种不同方式所求得的总和应是相等的，这叫计算两次原理成富比尼原理．计算两次可以建立左右两边关系不太明显的恒等式．在反证法中，计算两次又可用来构成矛盾．

例3 有一大筐苹果和梨分成若干堆，如果你一定可以找到这样的两堆，其苹果数之和与梨数之和都是偶数，问最少要把这些苹果和梨分成几堆？

解 （1）4堆是不能保证的．如4堆的奇偶性为：（反例） （奇奇），（偶偶），（奇偶），（偶奇）．

（2）5堆是可以保证． 因为苹果和梨数的奇偶性有且只有上述4种可能，当把这些苹果和梨分成5堆时，必有2堆属于同一奇偶性，其和苹果数与梨数都是偶数．

///xn，它们中的每一个要么是1，要么是?1．若例4 有n个数x1,x2,?,xn?1,x1x2?x2x3?????nxx?nxx0，求证4|n． ?1n1?证明 由xi??1,?1?，有xixi?1??1,?1?，再由

x1x2?x2x3?????xn?1xn?xnx1?0，

知n个xixi?1中有一半是1，有一半是?1，n必为偶数，设n?2k．

现把n个xixi?1相乘，有

??xn?1xn?xnx1?x1x2???xn?1xn?1， (?1)(?1)?x1x2?x2x3?可见，k为偶数，设k?2m，有n?4m，得证4|n．

例5 n个整数a1,a2,?,an?1,an，其积为n，其和为0，试证4|n．

证明 先证n为偶数，若不然，由a1a2?an?1an?n知，a1,a2,?,an?1,an全为奇数，其和必为奇数，与其和为0（偶数），故n必为偶数．（a1,a2,?,an?1,an中至少有1个偶数）

再证n为4的倍数，若不然，由n为偶数知，a1,a2,?,an?1,an恰有一个为偶数，其余

kk2222n?1个数全为奇数，奇数个奇数之和必为奇数，加上一个偶数，总和为奇数，与a1,a2,?,an?1,an之和为0矛盾，所以，n为4的倍数，4|n．,,a（a1,a2,?1n?an中至少有

21

2个偶数）

评析 要证4|n，只须证a1,a2,?,an?1,an中至少有2个偶数，分两步，第一步证至少有1个偶数，第二步证至少有2个偶数．

例6 在数轴上给定两点1和2，在区间(1,2)内任取n个点，在此n?2个点中，每相邻两点连一线段，可得n?1条互不重叠的线段，证明在此n?1条线段中，以一个有理点和一个无理点为端点的线段恰有奇数条．

证明 将n?2个点按从小到大的顺序记为A1,A2,…,An?2，并在每一点赋予数值ai，使

? 1, 当Ai为有理数点时，ai??

?1,　当A为无理数点时.i?与此同时，每条线段AiAi?1也可数字化为aiai?1（乘法）

??1,　当Ai,Ai?1一为有理数点，另一为无理数时，aiai?1??

? 1,　 当Ai,Ai?1同为有理数点或无理数点时,记aiai?1??1的线段有k条，一方面

(a1a2)(a2a3)(a3a4)…(an?1an?2)?(?1)k(?1)n?k?1?(?1)k

另一方面 (a1a2)(a2a3)(a3a4)…(an?1an?2) ?a1(a2a3…an?1)an?2?a1an?2??1， 得??1???1，故k为奇数． 评析 用了数字化、奇偶分析的技巧． 二、约数与倍数

最大公约数与最小公倍数的求法． （1）短除法．

（2）分解质因数法．设

k2a?p1?1p2?2?pk?k,?i?0,i?1,2,?,k， b?p1?1p2?2?pk?k,?i?0,i?1,2,?,k．

记 ?i?min??i,?i?,?i?max??i,?i?， 则 ?a,b??p11p22?pkk，

??? ?a,b??p11p22?pkk．

??? 22

（3）辗转相除法

?a,b???b,r???r1,r2?????rn?1,rn???rn,0??rn． 例7 （1）求?8381,1015?，?8381,1015?； （2）?144,180,108?，?144,180,108?． 解（1）方法1 分解质因数法．由

8381?172?29,1015?5?7?29,

得 ?8381,1015??29，

?8381,1015??5?7?172?29?293335．

方法2 辗转相除法．

88381101538120783 12612328

232232290q2?3q3?1q2?3q1?8 或

232261101583812322327838120

r4?0r2?29r2?232r1?261或 ?8381,1015???261,1015???261,232???29,232???29,0??29． ?8381,1015??8381?1015?8381,1015??8381?101529?8381?35?293335．（2）方法1 短除法．由

2144 180 108272 90 54336 30 27

312 10 9 4 5 3得 ?144,180,108??22?32?36，

?144,180,108??24?33?5?2160．

方法2 分解质因数法．由

23

144?24?32, 180?2?3?5,，

22108?22?33,得 ?144,180,108??2?3?36，

22?144,180,108??24?33?5?2160．

例8 正整数n分别除以2,3,4,5,6,7,8,9,10得到的余数依次为1,2,3,4,5,6,7,8,9，则

n的最小值为 ．

解 依题意，对最小的n，则n?1是2,3,4,5,6,7,8,9,10的公倍数

n?1?23?32?5?7，

得n?2519．

例9 有两个容器，一个容量为27升，一个容量为15升，如何利用它们从一桶油中倒出6升油来？

解 相当于求不定方程15x?27y?6的整数解． 由?15,27??3知，存在整数u,v，使

15u?27v?3，

可得一个解u?2,v??1，从而方程 15?4?27???2??6．

即往小容器里倒2次油，每次倒满之后就向大容器里倒，大容器倒满时，小容器里剩有3升油；再重复一次，可得6升．

例10 对每一个n?2，求证存在n个互不相同的正整数a1,a2,?,an，使

i,j??1,2,?,n?,i?j成立． ai?ajai?a，对任意的j 证明 用数学归纳法．当n?2时，取a1?1,a2?2，命题显然成立．

假设n?k时，命题成立，即存在a1,a2,?,ak，使 ai?ajai?aj，对任意的

i,j??1,2,?,k?,i?j成立．

现取b为a1,a2,?,ak及它们每两个数之差的最小公倍数，则k?1个数 b,a1?b,a2?b,?,ak?b

24

??at?b??b?at?b满足 ???b,????ai?b???a

j?b??ai?b???aj?b?, 即命题对n?k?1时成立．由数学归纳法知命题对n?2成立．

例11 ?1959,IMO21n?41?1?证明对任意正整数n，分数14n?3不可约．

证明1 （反证法）假若

21n?414n?3可约，则存在

d?1， ①

使 ?21n?4,14n?3??d， 从而存在p,q,?p,q??1，使

??21n?4?dp, ②14n?3?dq, ③ ?消去n，?3??3??2??2，得

1?d?3q?2p?， ④ 的 d?1． ⑤

由（1）、（5）矛盾，得d?1． 解题分析：（1）去掉反证法的假设与矛盾就是一个正面证法．

（2）式④是实质性的进展，表明

1?3?14n?3??2?21n?4?， 可见 ?21n?4,14n?3??1． 由此获得2个解法．

证明2 设?21n?4,14n?3??d．存在p,q,?p,q??1，使

??21n?4?dp, ①?14n?3?dq, ② 消去n，②×3-①×2，得

1?d?3q?2p? ③ 得 d?1．

证明3 由1?3?14n?3??2?21n?4? 得 ?21n?4,14n?3??1．

证明4 ?21n?4,14n?3?

25

??7n?1,14n?3? ④ ??7n?1,1? ⑤

?1．

解题分析：第④ 相当于 ①-②；第⑤ 相当于②-2（①-②）=②×3-①×2；所以③式与⑤式的效果是一样的．

例12 不存在这样的多项式

f?n??amn?am?1nmm?1???a1n?a0，

使得对任意的正整数n，f?n?都是素数．

证明 假设存在这样的多项式,对任意的正整数n，f?n?都是素数，则取正整数n?b，有素数p使

f?b??amb?am?1bmm?1???a1b?a0?p，

进而对任意的整数k,有

f?b?kp??am?b?kp??am?1?b?kp?mm?1???a1?b?kp??a0

??ambm?am?1bm?1???a1b?a0??Mp（二项式定理展开）

?P?1?M?，

其中M为整数，这表明f?b?kp?为合数．

这一矛盾说明，不存在这样的多项式,对任意的正整数n，f?n?都是素数． 三、平方数

若a是整数，则a就叫做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）?2n??0?mod4?,?2n?1??1?mod4?． （４）?2n?1??1?mod8?．

（6）凡是不能被3整除的数，平方后被3除余1．

（7）在两个相邻整数的平方数之间，不能再有平方数． （8）非零平方数的约数有奇数个．

2222 26

（9）直角三角形的三边均为整数时，我们把满足a?b?c的整数?a,b,c?叫做勾股

222数．勾股数的公式为

?a?m2?n2,? ?b?2mn,

?c?m2?n2,?其中m,n为正整数，?m,n??1且m,n一奇一偶．这个公式可给出全部素勾股数．

2．平方数的证明方法 （1）反证法． （2）恒等变形法．

（3）分解法．设a为平方数，且a?bc，?b,c??1，则b,c均为平方数． （4）约数法．证明该数有奇数个约数． 3．非平方数的判别方法

（1）若n?x??n?1?，则x不是平方数．

22（2）约数有偶数个的数不是平方数．

（3）个位数为2，3，7，8的数不是平方数． （4）同余法：满足下式的数n都不是平方数．

n?2?mod3?， n?2或3?mod4?， n?2或3?mod5?，

n?2或3或5或6或7?mod8?， n?2或3或7或8?mod10?．

（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的倍数的电灯的开关拉了一下，如此等等，最后那个学生走过来，把编号能被100整除的电灯的开关拉了一下，这样过去之后，问哪些灯是亮的？

讲解 （1）直接统计100次拉线记录，会眼花缭乱．

（2）拉电灯的开关有什么规律：电灯编号包含的正约数（学生）才能拉、不是正约数（学生）不能拉，有几个正约数就被拉几次．

27

（3）灯被拉的次数与亮不亮（开、关）有什么关系：

0 关 1 开 2 关 3 开 4 关 5 开 6 关 7 开 8 关 9 开

灯被拉奇数次的亮！

（4）哪些数有奇数个约数：平方数． （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为素数，求证2?a?b?1?为平方数．

证明 由勾股定理c?a?b，有 ?c?b??c?b??a，

2222但a为素数，必有

?c?b?a2, ?

?c?b?1,解得 b?12?a?1?， 2从而 2?a?b?1??2a?a?1?2??a?1?，

2??2为平方数．

例15 求证，任意3个连续正整数的积不是平方数．

证明 设存在3个连续正整数n?1,n,n?1（n?1）的积为平方数，即存在整数m，使

?n?1?n?n?1??m，

2即 n?1n?m，

2但n?1,n?1，故n?1,n均为平方数，有

2?2?2???n2?1?a2,?2 ?n?b,?m?ab,?得 1?n?a?n??n?1??2n?1?1，（注意n?1）

2222这一矛盾说明，3个连续正整数的积不是平方数．

28

例16 ?1986,IMO23?1?设d是异于2，5，13的任一整数．求证在集合?2,5,13,d?中可以找到两个不同元素a,b，使得ab?1不是完全平方数．

证明 因为2?5?1?3,2?13?1?5,5?13?1?8，所以不是完全平方数只能是

2222d?1,5d?1,13d?1．若结论不成立，则存在正整数x,y,z，使

2d?1?x2, ①5d?1?y2, ② 13d?1?z2, ③同时成立，由①知x是奇数，设x?2n?1代入①得 d?2n?2n?1

为奇数，代入②、③知y,z均为偶数．设y?2p,z?2q，代入②、③后相减，有 2d?q?p??q?p??q?p?．

222 由于2d为偶数，故p,q同奇偶，?q?p??q?p?可被4整除，得d为偶数．这与上证d为奇数矛盾．

所以，在集合?2,5,13,d?中可以找到两个不同元素a,b，使得ab?1不是完全平方数．

a2?b2例17 (IMO29?6)设a,b为正整数，ab?1整除a?b．证明是完全平方数．

ab?122a2?b2?k，k是正整数．式中a,b是对称的，不妨设a?b． 证明 令

ab?12a2?k??2?k?a2?k?k?1．本题获证． (l)若a?b，则2a?1 (2)若a?b，由带余除法定理，可设a?bs?t（s?2,0?t?b,s,t是整数)，则

a2?b2b2s2?2bst?t2?b2?为正整数，

ab?1b2s?bt?1b2s2?2bst?t2?b2??s?1? 由 2bs?bt?1 29

b2s22???2bst?t2?b2???b2s?bst?s???b2s?bt?1?b2s?bt?1 ??bst?t2?b2?s?b2s?bt?1b2s?bt?1

?s??b?b?t??1???b?b?t??t2?1b2s?bt?1?0,且 ?s?1??b2s2?2bst?t2?b2b2s?bt?1

?b222?s?bst?s???bs?bt?1???b2s2?2bst?t2?b2?b2s?bt?1bst?s?b2s?bt?1?t2?b2?b2s?bt?1bst?bt?t2

????s??b2s?b2??1b2s?bt?1?t??b?s?1??t???b?b?t??t2?1b2s?bt?1?0,1?b2s2?2bst?t2得 s??b2b2s?bt?1?s?1，

所以必有

b2s2?2bst?t2?b2b2s?bt?1?s， 化简 b2?t2?sbt?s，

得

b2?t2bt?1?s， 于是

a2?b2b2ab?1??t2bt?1?s， 其中t?b?a．

此时若t?0，则k?b2，本题获证．

若t?0，可继续令b?ts1?t1（s1?2,0?t1?t,s1,t1是整数），仿上可推得

a2?b2b2?t2t2?t2ab?1?1bt?1?tt1?s1，

1? 此时若t1?0，则k?t2，本题获证．

30

若t1?0，可如上法做下去．因t?t1?t2???0，且均为整数．故总能得到某个

ti?1?0，使k?ti2，是完全平方数．综上本题获证．

这种证明的方法叫“无穷递降法”，是17世纪法国数学家费马(Fermat．1601一1665)首创和应用的一种方法．

四．整除

整除的判别方法主要有7大类．

1．定义法．证ba?a?bq，有三种方式． （1）假设a?qb?r，然后证明r?0．（定理4） （2）具体找出q，满足a?bq． （3）论证q的存在．

例18 任意一个正整数m与它的十进制表示中的所有数码之差能被9整除． 证明 设m?an?10?an?1?10nn?1???a1?10?a0，其中0?ai?9,an?0，则

m??an?an?1???a1?a0? ?an10?1?an?110?n??n?1?1????a1?10?1?

???9?an?11?1??a?11?1???a?11?a??n?121?,n个1n?1个1??按定义 9m??an?an?1???a1?a0?． 2．数的整除判别法． （1）任何整数都能被1整除． （2）如果一个整数的末位能被2或５整除，那么这个数就能被2或５整除． （3）如果一个整数的末两位能被４或25整除，那么这个数就能被4或25整除． （4）如果一个整数的末三位能被8或125整除，那么这个数就能被8或125整除． （5）如果一个整数各数位上的数字之和能被3或9整除，那么这个数就能被3或9整除． 证明 由10?1?mod3?,10?1?mod9?，有 an?10n?an?1?10n?1???a1?10?a0?an?an?1???a1?a0?mod3?， an?10n?an?1?10n?1???a1?10?a0?an?an?1???a1?a0?mod9? （6）如果一个整数的末三位数与末三位数以前的数字所组成的数的差能被7或11或13整除，那么这个数就能被7或11或13整除． 证明 由m?anan?1?a2a1a0 ?anan?1?a3?1001?anan?1?a3?a2a1a0，

31

??知 1001anan?1?a3a2a1a0?1001anan?1?a3??a2a1a0， 又由1001?7?11?13，而7,11,13均为素数知，m能被7或11或13整除． （7）如果一个整数的奇位数字之和与偶位数字之和的差能被11整除，则这个数能被??11整除． 证明 由10??1?mod11?，有 an?10n?an?1?10n?1???a1?10?a0

?ann??1??an?1??1?n?1???a1??1??a0?mod11?.3．分解法．主要用乘法公式．如

an?bn??a?b??an?1?an?2b?an?3b2???abn?2?bn?1?．

a2n?1?b2n?1??a?b??a2n?2?a2n?3b?a2n?4b2???ab2n?3?b2n?2?．

a2n?b2n??a?b??a2n?1?a2n?2b?a2n?3b2???ab2n?2?b2n?1?．

例19 试证?1?2???9??15?25???95?．

证明 改证45?15?25???95?．设S?15?25???95，则

S??15?85???25?75???35?65???45?55??95 ??1?8?m1??2?7?m2??3?6?m3??4?5?m4?95

?9?m1?m2?m3?m4?94?,得9S．

又 S??15?95???25?85???35?75???45?65??55

??1?9?m1??2?8?m2??3?7?m3??4?6?m4?55?5?2m

1?2m2?2m43?2m4?5?,得5S．

但?9,5??1，得45S，即?1?2???9??15?25???95?．

例20 ?1979,IMO21?1?设p与q为正整数，满足

p11q?1?2?3???111318?1319， 32

求证p可被1979整除（1979p）

证明

p1111?1?????? q2313181319??1111??111???????2??????? 2313181319??241318? ??1?11??111??11??1???????1????????

13181319??23659??231111 ?????66066113181319660?1319661?1318989?990 ?????660?1319661?1318989?990?M660?661???1319

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

m11的分子m是吉祥数． ?1????n220090908m11证明：由?1????

n2200909081111?1??1??????????????????120090908??220090907??1004545410045455?200909092009090920090909 ?????1?200909082?2009090710045454?10045455p?20090909?,1?2???20090907?20090908其中p为正整数，有

20090909?n?p?1?2???20090907?20090908?m，

这表明，20090909整除1?2???20090907?20090908?m，但20090909为素数，不能整除1?2???20090907?20090908，所以20090909整除m，得m是吉祥数．

4． 余数分类法．

例21 试证3n?n?1??2n?1?．

证明1 任何整数n被3除其余数分为3类

33

n?3k,n?3k?1,n?3k?2,k?Z， （1）n?3k时，有

n?n?1??2n?1??3??k?3k?1??6k?1???, 有3n?n?1??2n?1?． （2）n?3k?1时，有

n?n?1??2n?1??3???3k?1??3k?2??2k?1???,

有3n?n?1??2n?1?． （3）n?3k?2

n?n?1??2n?1??3???3k?2??k?1??6k?5???,

有3n?n?1??2n?1?． 综上得，3n?n?1??2n?1?． 证明2 n?n?1??2n?1??2n?2n?2??2n?1?4，

得 32n?2n?2??2n?1?， 又?3,4??1，得

3n?n?1??2n?1?．

5．数学归纳法． 6．反证法． 7．构造法．

例22 k个连续整数中必有一个能被k整除． 证明 设k个连续整数为

a,a?1,a?2,?,a?k?1，

若这k个数被k除没有一个余数为0，则这k个数的余数只能取1,2,?,k?1，共k?1种情况，必存在两个数

a?i,a?j,0?i?j?k ， 使 a?i?kq1?r,

a?j?kq2?r,

34

其中q1?q2，相减

i?j?k?q1?q2?， 有 i?j?kq1?q2?k， 即 i?j?k

与i?j?k矛盾．故k个连续整数中必有一个能被k整除． 也可以由i?j?k?q1?q2?得 0?i?j?k?q1?q2??k， 推出0?q1?q2?1，与q1?q2为整数矛盾． 例23 k个连续整数之积必能被k!整除． 证明 设k个连续整数为

n,n?1,n?2,?,n?k?1， （1）若这k个连续整数为正整数，则

n?n?1??n?2???n?k?1?k!?n!k!?n?k?!??C?

kn只须证明，对任何一个素数p，分子中所含p的方次不低于分母中所含p的方次，由高斯函数的性质?x?y???x???y?，有

kn?k??n?k???n??k??n?k??????ps???ps???ps???ps? ????????得

C为整数（证实了组合数的实际意义）

（2）若这k个连续整数中有0，则连乘积为0，必能被k!整除．

（3）若这k个连续整数为负整数，则

n?n?1??n?2???n?k?1? ???1?kk!??n???n?1???n?2????n?k?1?k!

???1?由（1）知

kCk?n,n?n?1??n?2???n?k?1?k!为整数．

Ck为整数，故?n例24 有男孩、女孩共n个围坐在一个圆周上（n?3），若顺序相邻的3人中恰有一

35

个男孩的有a组，顺序相邻的3人中恰有一个女孩的有b组，求证3a?b．

证明 现将小孩记作ai(i?1,2,…,n)，且数字化

?1,　ai表示男孩时ai??

?1, a表示女孩时i?则“3人组”数值化为

Ai?ai?ai?1?ai?2?3,　　 ai,ai?1,ai?2均为男孩???3,　　ai,ai?1,ai?2均为女孩 ???1,　　 ai,ai?1,ai?2恰有一个女孩??1,　　a,a,a恰有一个男孩ii?1i?2?其中an?j?aj．

又设取值为3的Ai有p个，取值为?3的Ai有q个，依题意，取值为1的Ai有b个，取值为?1的Ai有a个，得

a1?a2?…?an)?a(1?a??)a(?2a?a?4…)?an?(a?a1 3(2a33 ?3p?(?3)q?(?1)a?b?3(p?q)?(b?a)， 可见3a?b．

例25 （1956，中国北京）证明n?除时余2．

分析 只需说明

3)321n?n?1对任何正整数n都是整数，并且用322n?3n?1?321n?n?为整数，但不便说明“用3除时余2”，应说明222n?n?1??2n?1?31n3?n2?n?是3的倍数．作变形

222 n?32n?2n?2??2n?1?321n?n?1??1,?3,8??1 ， 228命题可证．

证明 已知即

n?n?1??2n?1?31n3?n2?n?1??1， ①

222因为相邻2个整数n,?n?1?必有偶数，所以n?3321n?n?1为整数．又①可变为 2236

2n?2n?2??2n?1?31n3?n2?n?1??1，

228因为相邻3个整数2n,?2n?2?,?2n?1?必有3的倍数，故2n?2n?2??2n?1?能被3整除；又?3,8??1，所以

2n?2n?2??2n?1?8能被3整除；得n3?321n?n?1用3除时22余2．

五、同余

根据定义，同余问题可以转化为整除问题来解决；同时，同余本身有很多性质，可以直接用来解题．

例26 正方体的顶点标上?1或?1，面上标上一个数，它等于这个面四个顶点处的数的乘积，求证，这样得出的14个数之和不能为0．

证明 记14个数的和为S，易知，这14个数不是?1就是?1，若八个顶点都标上?1，则S?14，命题成立．

对于顶点有?1的情况，我们改变?1为?1，则和S中有4的数a,b,c,d改变了符号，用S表示改变后的和，由

a?b?c?d?0?mod2?，

知 S?S?2a?b?c?d?0?mod4?，

//这表明，改变一个?1，和S关于模4的余数不变，重复进行，直到把所有的?1都改变为?1，则

S?S/?1?1???1?14?2?mod4?，

所以，S?0．

例27 设多项式f?x??a0x?a1xnn?1???an?1x?an的系数都是整数，并且有一个

奇数?及一个偶数?使得f???及f???都是奇数，求证方程f?x??0没有整数根．

证明 由已知有

f????1?mod2??a0?a1?a2???an?1?mod2?， ①

f????1?mod2??an?1?mod2?， ②

若方程f?x??0存在整数根x0，即f?x0??0． 当x0为奇数时，有

f?x0??0?mod2??a0?a1?a2???an?0?mod2?，

37

与①矛盾．

有x0为偶数时，有

f?x0??0?mod2??an?0?mod2?，

与②矛盾．

所以方程f?x??0没有整数根．

六、不定方程

未知数的个数多于方程个数的整系数代数方程，称为不定方程．求不定方程的整数解，叫做解不定方程． 解不定方程通常要解决3个问题，方程是否有解？有解时，有几个解，解数是有限还是无穷？求出全部解．

例28 解方程7x?19y?213． 解法1 由?7,19??1知方程有整数解． 观察特解，列表

y 1 2 x 19725 3 ? 7

?x0?25,?x?25?19t,得一个特解?从而通解为?

y?2,y?2?7t.??0方法总结：第1步，验证?a,b?c，经常是?a,b??1． 第2步，求特解（观察、列举、辗转相除等）．

第3步，代入公式．

解法2 由?7,19??1知方程有整数解． 用辗转相除法求特解，再得通解．先求 7x?19y?1 的一个解，由

19?2?7?5 7?1?5?2

5?2?2?1逆过来有

1?5?2?2?5??7?5??2?5?3?7?2 ??19?2?7??3?7?2

?19?3?7???8?

38

同乘以213，有

7??8?213??19?3?213??213， 得 ??x??1704?19t,

y?639?7t.?解法3 由?7,19??1知方程有整数解． 用柯西方法求特解，将方程变为 x?令

213?19y3?2y， ?30?3y?773?2y?t1为整数，有 77t?3t?1 y?1， ?3t1?1?122t?1令1?t2为整数，有

2 t1?2t2?1

代入得y?2?7t2,x?25?19t2．

方法总结：第1步，将系数较小的那个未知数用另一个未知数来表示

第2步，将表达式形式分离为整数部分与分数部分（实际上也是整数）设分数部分为t1，又得一个不定方程．

第3步，重复上述步骤，设逐次的分数部分为t2,t3,?,tn，那么方程的系数越来越小；对?a,b??1，经过有限次操作，最后方程的两个未知数中必有一个系数为1，从而得到

tn?1?dtn?e，（d,e为整数）

第4步，将上式按顺序倒代上去，逐步求出tn?2,?,t2,t1,x,y，即得不定方程整数解得通解

解法4 用同余法，由7x?19y?213有 19y?213?3?38?mod7? ， 但?7,19??1，有

y?2?mod7?，

得 y?2?7t，

39

进而 x?213?19y213?19?2?7t???25?19t．

77方法总结：ax?by?c?ax?c?modb?或by?c?moda?． 例29 求方程x?2xy?2009的整数解． 解 由2009的分解式，有 x232?x?2y??12?2009?72?41，

?x2?1,?x?1,?x??1,??有 ? ?y?1004,y?1005,??x?2y?2009,??x2?72,?x?7,?x??7,? ????x?2y?41,?y?17,?y?24.例30 甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛，双方先由1号队员比赛，负者被淘汰，胜者再与负方2号队员比赛，?直到有一方队员全被淘汰为止，另一方获得胜利，形成一种比赛过程，那么所有可能出现的比赛过程的种数为 ．（1988，高中联赛）

解法1 设甲、乙两队的队员按出场顺序分别为A1,A2,A3,A4,A5,A6,A和

B1,B2,B3,B4,B5,B6,B7．如果甲方获胜，设Ai获胜的场数是xi，则0?xi?7,1?i?7而

且

x1?x2???x7?7 ， ①

容易证明以下两点：在甲方获胜时

（i）不同的比赛过程对应着方程①的不同非负整数解；

（ii）方程①的不同非负整数解对应着不同的比赛过程，例如，解（2，0，0，1，3，1，0）对应的比赛过程为：A1胜B1和B2；B3胜A1、和A3；A4胜B3后负于B4；A5胜B4、B5和B6但负于B7；最后A6胜B7结束比赛．下面求方程①的非负整数解个数，设yi?xi?1，问题等价于方程

y1?y2?y3?y4?y5?y6?y7?14，

正整数解的个数，将上式写成

1?1?1?1?1?1?1?1?1?1?1?1?1?1?14，

从13个加号取6个的方法数C13种．得甲方获胜的不同的比赛过程有C13种．

同理，乙方获胜的不同的比赛过程也有C13种，合计2C13?3432种比赛过程 解法2 设甲、乙两队的队员按出场顺序分别为A1,A2,A3,A4,A5,A6,A和

40

7666

本文来源：https://www.bwwdw.com/article/c933.html