haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 初中教育 > 学科竞赛学科竞赛

数学竞赛中的数论问题

发布时间:2013-12-28 09:01:55  

数学竞赛中的数论问题

罗增儒

引言

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

什么是正整数呢?人们借助于“集合”和“后继”关系给正整数(当时也即自然数)作过本质的描述,正整数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?a

b???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?矛盾. aba,ba,bq

两步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?

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?

定理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,且b,a,则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,,均为整数,且 kkk

10

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?1

a2n?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(2进制)

定理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

??p

2

?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|Ci

p?i?1,2,?,p?1?,故有

?k?1?p?kp?C1p?1

pk???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?k

k?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恰有一个为偶数,其余

kk2222

n?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

,在区间内任取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)分解质因数法.设 k2

a?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 辗转相除法.

8838110153

8120783

12612328

232232

290

q2?3q3?1q2?3q1?8

或 23226110158381

2322327838120

r4?0r2?29r2?232r1?261

或 ?8381,1015???261,1015???261,232???29,232???29,0??29. ?8381,1015??8381?1015

8381,1015?8381?1015

29?8381?35?293335.

(2)方法1 短除法.由

2144 180 108

272 90 54

336 30 27

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,, 22

108?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?4

1?1?证明对任意正整数n,分数14n?3不可约.

证明1 (反证法)假若21n?4

14n?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?.

(4)?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)灯被拉的次数与亮不亮(开、关)有什么关系:

灯被拉奇数次的亮!

(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,所以不是完全平方数只能是222

2d?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?122

a2?b2

?k,k是正整数.式中a,b是对称的,不妨设a?b. 证明 令ab?1

2a2

?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?1

b2s2?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?1

b2s?bt?1 ?s??b?b?t??1???b?b?t??t2?1

b2s?bt?1?0,

且 ?s?1??b2s2?2bst?t2?b2

b2s?bt?1

?b222

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

b2s?bt?1

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

?b2s?bt?1

bst?bt?t2

????s??b2s?b2??1

b2s?bt?1

?t??b?s?1??t???b?b?t??t2?1

b2s?bt?1?0,

1?b2s2?2bst?t2

得 s??b2

b2s?bt?1?s?1, 所以必有b2s2?2bst?t2?b2

b2s?bt?1?s,

化简 b2?t2?sbt?s,

得 b2?t2

bt?1?s,

于是 a2?b2b2

ab?1??t2

bt?1?s,

其中t?b?a.

此时若t?0,则k?b2,本题获证. 若t?0,可继续令b?ts1?t1(s1?2,0?t1?t,s1,t1是整数),仿上可推得

a2?b2b2?t2t2?t2

ab?1?1

bt?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?.

31

an?10n?an?1?10n?1???a1?10?a0 ?an

n??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?2m4

3?2m4?5?,

得5S.

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

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

p11

q?1?2?3???11

1318?1319,

32

求证p可被1979整除(1979p)

证明 p1111?1??? q2313181319

?

?1111??111???????2??????? 2313181319??241318? ??1?

11??111??11??1???????1???????? 13181319??23659??23

1111 ?????66066113181319

660?1319661?1318989?990 ?????660?1319661?1318989?990?

M

660?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????n220090908

m11证明:由?1???? n220090908

1111?1??1??????????????????120090908??220090907??1004545410045455?

200909092009090920090909 ?????1?200909082?2009090710045454?10045455

p?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? k

n

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

k

n?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”,应说明222

n?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为整数.又①可变为 22

36

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知方程有整数解.

观察特解,列表

?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为整数,有 7

7t?3t?1 y?1, ?3t1?1?1

22

t?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的分解式,有 x

2

32

?x?2y??1

2

?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

7

6

6

6

B1,B2,B3,B4,B5,B6,B7.每一个比赛过程对应着这14个元素的一个排列,且满足Ai的下

标从左到右是递增的,Bi的下标从左到右也是递增的.

由于从14个位置中取出7个来,有序地排上A1,A2,A3,A4,A5,A6,A7有C14种排法,而剩下的7个位置有序地排上B1,B2,B3,B4,B5,B6,B7只有一种排法,所以,问题的实质是从14个相异元素中取出7个的组合数,得C14?3432种比赛过程.

解法3 建立下面的对应;集合?A1,A2,…,A7?的任一个7元可重组合对应着一个比赛过程,且这种对应也是一个一一对应.例如前述的比赛过程对应的7长可重组合是

7

7

?A1,A1,A4,A5,A5,A5,A6?,所以甲方获胜的不同的比赛过程的总数就是集合

77

?A1,A2,…,A?7的7长可重组合的个数C7?7?1?C13.

同理,乙方获胜的不同的比赛过程也有C13种,合计2C13?3432种比赛过程. 例31(1989,高中)如果从数1,2,?,14中按由小到大的顺序取出a1,a2,a3,使同时满足

a2?a1?3, a3?a2?3, 那么,所有符合上述要求的不同取法有多少种? 解 由已知得

77

a1?1?0, a2?a1?3?0 a3?a2?3?0, 14?a3?0,

4项均为非负数,相加得

?a1?1???a2?a1?3???a3?a2?3??? 14?a3??7,

于是a1,a2,a3的取法数就是不定方程 x1?x2?x3?x4?7

的非负整数解的个数,作一一对应y1?xi?1,

问题又等价于不定方程 y1?y2?y3?y4?11 的正整数解.由

41

1?1???1?11,

得C10个解,即符合要求的不同取法有C10种.

七.数论函数

主要是?x?高斯函数,??n?欧拉函数.

例32 某学校要召开学生代表大会,规定各班每10人推选一名代表,当各班人数除以10的余数大于时再增选一名代表.那么,各班可推选代表人数y与该班人数x之间的函..6.

数关系用取整函数y??x?(?x?表示不大于x的最大整数)可以表示为 (A)y??33?x??x?3??x?4??x?5? (B) (C) (D) y?y?y?????????10??10??10??10?(2010年全国高考数学陕西卷理科第10题)

解法1 选(B).(求解对照).规则是“六舍七入”,故加3即可进1. 选y???x?3?. ?10??

解法2 选(B).(特值否定).取x?56,按规定应选5人,可否定(C)、(D);再取x?57,按规定应选6人,可否定(A).

注:主要错误选(C) ,误为“五舍六入”.

例33 用?x?表示不大于x的最大整数,求 ??1??2??2004????????366??366???366????????. ?366??????

讲解 题目的内层有2004个高斯记号,外层1个高斯记号.关键是弄清?x?的含义,进而弄清加法谁与谁加、除法谁与谁除:

(1)分子是那些数相加,求出和来;

由366?5?1830?2004?2196?366?6,知分子是0~5的整数相加,弄清加数各有几个

(2)除法谁除以366,求出商的整数部分.

42

原式???0?365?366?1?2?3?4??5?175?? 366???10?366?875????366??

143????10?2? ?366??

?12.

命题背景2004年有12个月、366天.

例34 50!的标准分解式中2的指数.

解 50!?2132537411513617719823929?31?37?41?43?47

2的指数为 ?????????

?50??50??50??50??50???2???3???4???5??25?12?6?3?1?47. ???2??2??2??2??2?

图示(5条横线,25个偶数中2的方次,按横线求和)

八、综合练习

例35 整数勾股形中,证明

(1)必有一条直角边长是3的倍数;

(2)必有一条直角边长是4的倍数;

(3)必有一条边长是5的倍数;

(4)三角形的面积是6的倍数.

证明 当整数勾股形的三边有公约数时,可以先约去,使三边长x,y,z互素,且满足

x2?y2?z2.

这时,若x,y两个均为偶数,则z也为偶数,与x,y,z互素矛盾;若x,y两个均为奇数,有

x?1?mod4?,y?1?mod4?, 22

得 z?x?y?2?mod4?, 222

这与平方数模4只能取0,1矛盾.所以,x,y中有且只有一个为偶数,不妨设x为偶数.

(1)设x,y中无一为3的倍数,则

x?1?mod3?,y?1?mod3?, 22

得 z?x?y?2?mod3?, 222

这与平方数模3只能取0,1矛盾,故x,y中有一个为3的倍数.

(2)由x为偶数.,必有y,z均为奇数,记

x?2m,y?2p?1,z?2q?1

222222有 4m?x?z?y??2q?1???2p?1??4q?q?p?p 22??

43

则 m?q?q?1??p?p?1? 2

右边是两个偶数的差,必为偶数,从而x为4的倍数.

(3)若x,y中有5的倍数,命题已成立. 若x,y均不是5的倍数,则若x,y只能是形如5k?1或5k?2的正整数.

若x,y均为5k?1型,则

z2?x2?y2?1?1?2?mod5?

这与平方数模5只能取0,1,4矛盾

若x,y均为5k?2型,则

z2?x2?y2?4?4?3?mod5?

这与平方数模5只能取0,1,4矛盾.

所以,x,y只能分别取5k?1与5k?2型,有

z?x?y?4?1?0?mod5? 222

得5z,但5是素数,得5z.

(4)由上证(1)、(2)及?3,4??1知,xy是12的倍数,则

形的面积是6的倍数.

例36 已知?ABC内有n个点,连同A,B,C共有n?3个点,以这些点为顶点,把21xy是6的倍数,得三角2?ABC分割为若干个互不重叠的小三角形,现把A,B,C分别染上红色、蓝色、黄色,而其余n个点,每点任意染上红、蓝、黄三色之一,证明三顶点都不同色的小三角形的总数必是奇数.(斯潘纳定理)

证明1 给这些小三角形的边赋值:当边的两端点同色时,记为0;当边的两端点异色时,记为1;

再用三边之和给小三角形赋值:当三角形的三顶点同色时,和值为0,记这样的小三角形有a个;当三角形的三顶点中仅有两点同色时,和值为2,记这样的小三角形有b个;当三角形的三顶点两两异色时,和值为3,记这样的小三角形有c个.下面用两种方法计算所有三角形赋值的总和S,一方面

S?0?a?2?b?3?c?2b?3c. ①

另方面,AB,BC,CA的赋值均为1,和为奇数;而?ABC内的每一条连线,在上述S的计算中都被计算了两次,和为偶数;这两者之和得S为奇数,记为

S?2k?1 ②

由①,②得

2k?1?2b?3c

可见c为奇数,即三顶点都不同色的小三角形的总数必是奇数.(

44

证明2 设大三角形内部的红蓝边(一个端点红色、另一端点蓝色)有k条.又设三个顶点分别为红、黄、蓝的小三角形有p个,三个顶点分别为红、红、蓝或红、蓝、蓝的小三角形有q个,其余的小三角形有r个.下面,用两种方法来计算红蓝边的条数e,一方面,逐一计算每个小三角形的红蓝边,再求和,得

e?p?2q.

另方面,每一条红蓝边在大三角形内部都被计算了两次,而大三角形本身的红蓝边只计算了计算了一次,故

e?2k?1,

有 p?2q?2k?1,

即 p?2?k?q??1,

这表明,三顶点都不同色的小三角形的总数必是奇数.(斯潘纳定理)

例37 对整点25边形的顶点作三染色,求证,存在一个三顶点同色的三角形,它的重心也是整点.

解 对25个顶点作三染色,必有9个顶点同色,不妨设Ai?xi,yi?,i?1,2,?,9同红色,下面证明,必存在一个同红色的?AiAjAk?1?i?j?k?9?,其重心?xi?xj?xkyi?yj?yk,?33???也是整点.

?

(1)若A1,A2,?,A9的横(纵)坐标中有5个对模3同余,不妨设

x1?x2?x3?x4?x5?mod3?,

这时,由于y1,y2,y3,y4,y5中必有3个数其和能被3整除,设

3|(yi?yj?yk)?1?i?j?k?5?,

则?AiAjAk重心也是整点.

同理,若纵坐标中有5个对模3同余,结论同样成立.

(2)若A1,A2,?,A9的横坐标中任意5个对模3不同余,并且纵坐标中任意5个也对模3不同余,则横坐标中最多有4个对模3同余,因而x1,x2,?,x9被3除时,余数取遍0,1,2,同样,y1,y2,?,y9被3除时,余数也取遍0,1,2.从而,xi中至少有两种余数出现3次,不妨设

??mo?d,3 x1?x2?x30

? x4?x5?x61 ?mo?d.3

45

这时,若y1?y2?y3?mod3?或y4?y5?y6?mod3?有一个成立,命题已真.否则y1,y2,y3对模3至少有两个余数,记为?,???0,1,2?,且??,?,????0,1,2?.同样,y4,y5,y6对模3也至少有两个余数,或为?,?,或为?,?,或为?,?.也就是说y1,y2,y3,y4,y5,y6对模3的余数只有两种可能:

①包括全部??,?,????0,1,2?;

②只包括?,?,但每一个重复2次~4次. 这时取k??7,8,9?,使xk?2?mod3?,则存在i,j满足1?i?3?j?6,使

xi?xj?xk?0?1?2?0?mod3?,

?

且使 y???????0?mod3?,

i?yj?yk????????0?mod3?,

????????0?mod3?,

其中之一成立,从而?AiAjAk重心也是整点.

46

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com