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

初中数论讲义

发布时间:2013-12-30 09:46:48  

第一讲 奇数与偶数

整数按能否被2整除可分为两类,一类余数为0,称为偶数,一类余数为1,称为奇数. 偶数可以表示为2n,奇数可以表示为2n?1或2n+1.

一般地,整数被正整数m去除,按照余数可以分为m类,称为模m的剩余类Ci={xx≡i(modm)},从每类中各取出一个元素ai∈Ci,可得模m的完全剩余系(剩余类派出的一个代表团),0,1,2,L,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

…… m222kkn(2k?1).

1

例1 (1906,匈牙利)假设a1,a2,L,an是1,2,L,n的某种排列. 证明:

如果n是奇数,则乘积(a1?1)(a2?2)L(an?n)是偶数.

解法1 (反证法)假设(a1?1)(a2?2)L(an?n)为奇数,则ai?i均为奇数,奇数个奇数的和还是奇数

奇数=(a1?1)+(a2?2)+L+(an?n)

=(a1+a2+L+an)?(1+2+L+n)=0,

这与“奇数≠偶数”矛盾. 所以(a1?1)(a2?2)L(an?n)是偶数.

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

解法2 (反证法)假设(a1?1)(a2?2)L(an?n)为奇数,则ai?i均为奇数,ai与i的奇偶性相反,{1,2,L,n}中奇数与偶数一样多,n为偶数.但已知条件n为奇数,矛盾. 所以(a1?1)(a2?2)L(an?n)是偶数.

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

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

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

练习 1-1(1986,英国)设a1,a2,L,a7是整数,b1,b2,L,b7是它们的一个排列,证明(a1?b1)(a2?b2)L(a7?b7)是偶数.

练习1-2 π的前24位数字为π=3.14159265358979323846264,记a1,a2,L,a24为该24个数字的任一排列,求证(a1?a2)(a3?a4)L(a23?a24)必为偶数.

2

例2 能否从1,2,L,15中选出10个数填入图的圆圈中,使

得每两个有线相连的圈中的数相减(大数减小数),所得的14

个差恰好为1,2,L,14?

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

S=1+2+L+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堆属于同一奇偶性,其和苹果数与梨数都是偶数.

例4 有n个数x1,x2,L,xn?1,xn,它们中的每一个要么是1,要么是?1.若///

x1x2+x2x3+L+L+xn?1xn+xnx1=0,求证4|n.

证明 由xi∈{1,?1},有xixi+1∈{1,?1},再由

x1x2+x2x3+L+L+xn?1xn+xnx1=0,

知n个xixi+1中有一半是1,有一半是?1,n必为偶数,设n=2k.

现把n个xixi+1相乘,有

(?1)(+1)=x1x2gx2x3gLgxn?1xngxnx1=x1x2gLgxn?1xn=1,

可见,k为偶数,设k=2m,有n=4m,得证4|n.

kk2222

3

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

证明 先证n为偶数,若不然,由a1a2Lan?1an=n知,a1,a2,L,an?1,an全为奇数,

其和必为奇数,与其和为0(偶数),故n必为偶数.(a1,a2,L,an?1,an中至少有1个偶数)

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

n?1个数全为奇数,奇数个奇数之和必为奇数,加上一个偶数,总和为奇数,与a1,a2,L,an?1,an之和为0矛盾,所以,n为4的倍数,4|n.(a1,a2,L,an?1,an中至少有2个偶数)

评析 要证4|n,只须证a1,a2,L,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, 当Ai为无理数点时.

与此同时,每条线段AiAi+1也可数字化为aiai+1(乘法)

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

? 1, 当Ai,Ai+1同为有理数点或无理数点时,

记aaii+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为奇数.

评析 用了数字化、奇偶分析的技巧. k2

4

第二讲 约数与倍数

最大公约数与最小公倍数的求法.

(1)短除法.

(2)分解质因数法.设

a=p1α1p2α2Lpkαk,αi≥0,i=1,2,L,k,

b=p1β1p2β2Lpkβk,βi≥0,i=1,2,L,k.

记 γi=min{αi,βi},δi=max{αi,βi},

则 (a,b)=p11p22Lpkk, γγγ

[a,b]=p11p22Lpkk. δδδ

(3)辗转相除法

(a,b)=(b,r)=(r1,r2)=L=(rn?1,rn)=(rn,0)=rn. 例7 (1)求(8381,1015),[8381,1015];

(2)(144,180,108),[144,180,108].

解(1)方法1 分解质因数法.由

8381=172×29?2??(8381,1015)=29,[8381,1015]=5×7×17×29=2933351015=5×7×29?

方法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×10158381×1015==8381×35=293335. 8381,101529 5

(2)方法1 短除法.由

2144 180 108

272 90 54

336 30 27

4 5 3

得 (144,180,108)=2×3=36, 22

[144,180,108]=24×33×5=2160.

方法2 分解质因数法.由

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,L,an,使ai?ajai+aj,对任意的i,j∈{1,2,L,n},i≠j成立.

6

证明 用数学归纳法.当n=2时,取a1=1,a2=2,命题显然成立. 假设n=k时,命题成立,即存在a1,a2,L,ak,使 ai?ajai+aj,对任意的i,j∈{1,2,L,k},i≠j成立.

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

?

满足 ?(at+b)?b(at+b

?)+b,??(ai+b)?(a+(a

j+b)(ai+b)j+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, ①

3=dq, ②

?14n+

7

消去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)

=(7n+1,14n+3) ④

=(7n+1,1) ⑤

=1.

解题分析:第④ 相当于 ①-②;第⑤ 相当于②-2(①-②)=②×3-①×2;所以③式与⑤式的效果是一样的.

例12 不存在这样的多项式

f(n)=amn+am?1nmm?1+L+a1n+a0,

使得对任意的正整数n,f(n)都是素数.

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

f(b)=amb+am?1bmm?1+L+a1b+a0=p,

进而对任意的整数k,有

f(b+kp)=am(b+kp)+am?1(b+kp)mm?1+L+a1(b+kp)+a0

=(ambm+am?1bm?1+L+a1b+a0)+Mp(二项式定理展开)

=P(1+M),

其中M为整数,这表明f(b+kp)为合数.

这一矛盾说明,不存在这样的多项式,对任意的正整数n,f(n)都是素数. 8

三、平方数

若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)非零平方数的约数有奇数个.

(9)直角三角形的三边均为整数时,我们把满足a+b=c的整数(a,b,c)叫做勾股2222222

数.勾股数的公式为

?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),

9

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)拉电灯的开关有什么规律:电灯编号包含的正约数(学生)才能拉、不是正约数(学生)不能拉,有几个正约数就被拉几次.

(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个灯还亮.

斜边为正整数c,若a为素数,例14 已知直角三角形的两条直角边分别为正整数a,b,求证2(a+b+1)为平方数.

证明 由勾股定理c=a+b,有 (c+b)(c?b)=a,

2

2

2

2

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

10

使

(n?1)n(n+1)=m, 2

即 n2?1n=m2,

但n?1,n=1,故n?1,n均为平方数,有 ()(2)2

?n2?1=a2,?2 ?n=b,

?m=ab,?

得 1=n?a≥n?(n?1)=2n?1>1,(注意n>1) 2222

这一矛盾说明,3个连续正整数的积不是平方数.

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

证明 因为2×5?1=32,2×13?1=52,5×13?1=82,所以不是完全平方数只能是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

11

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+

ab+1=t2+b2

b2s?bt+1为正整数,

由 b2s2?2bst+t2+b2

b2s?bt+1?(s?1)

(b2s22

=?2bst+t2+b2)?(b2s2?bst+s)+(bs?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,

b2s2?2bst+t2

s+1)?+b2

且 (b2s?bt+1

b222

=(s?bst+s)+(b2s?bt+1)?(b2s?2bst+t2+b2)

b2s?bt+1

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

=b2s?bt+1

bst?bt?t2)+s+(b2

=(s?b2)+1

b2s?bt+1

=t?b(s?1)?t?+b(b?t)+t2+1

b2s?bt+1>0,

b2s2

得 s?1<?2bst+t2+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+t2

ab+1=bt+1=s,

12

其中t<b<a.

此时若t=0,则k=b,本题获证.

若t>0,可继续令b=ts1?t1(s1≥2,0≤t1<t,s1,t1是整数),仿上可推得 2

a2+b2b2+t2t2+t12===s1, ab+1bt+1tt1+1

此时若t1=0,则k=t,本题获证.

若t1>0,可如上法做下去.因t>t1>t2>L≥0,且均为整数.故总能得到某个2ti+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+L+a1×10+a0,其中0≤ai≤9,an≠0,则

m?(an+an?1+L+a1+a0)

=an10?1+an?110(n)(n?1?1)+L+a1(10?1)

??=9?an×11L1?+a×11L1+L+a×11+a{n?1{21?,

n个1n?1个1??

按定义 9m?(an+an?1+L+a1+a0). 2.数的整除判别法.

(1)任何整数都能被1整除.

(2)如果一个整数的末位能被2或5整除,那么这个数就能被2或5整除.

(3)如果一个整数的末两位能被4或25整除,那么这个数就能被4或25整除.

(4)如果一个整数的末三位能被8或125整除,那么这个数就能被8或125整除.

(5)如果一个整数各数位上的数字之和能被3或9整除,那么这个数就能被3或9整除.

证明 由10≡1(mod3),10≡1(mod9),有

13

an×10n+an?1×10n?1++a1×10+a0

≡an(?1)+an?1(?1)nn?1+L+a1(?1)+a0(mod11).

3.分解法.主要用乘法公式.如 an?bn=(a?b)(an?1+an?2b+an?3b2+L+abn?2+bn?1).

a2n?1+b2n?1=(a+b)(a2n?2?a2n?3b+a2n?4b2?L?ab2n?3+b2n?2).

a2n?b2n=(a+b)(a2n?1?a2n?2b+a2n?3b2?L+ab2n?2?b2n?1).

例19 试证(1+2+L+9)1+2+L+955(5).

+25+L+95,则 证明 改证451+2+L+9(555).设S=15

S=(15+85)+(25+75)+(35+65)+(45+55)+95

=(1+8)m1+(2+7)m2+(3+6)m3+(4+5)m4+9 5

=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(2m1+2m2+2m3+2m4+5),4

14

得5S.

但(9,5)=1,得45S,即(1+2+L+9)1+2+L+955(5).

例20 (1979,IMO21?1)设p与q为正整数,满足 p1111=1?+?L?+, q2313181319

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

证明 p1111=1?+?L?+ q2313181319

?

?1111??111?++L++?2+?L+??? 2313181319??241318? =?1+

11??111??11=?1+++L++?1++?L+??? 231318131923659????

1111++L++ 66066113181319

660+1319661+1318989+990=++L+ 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=1++L+的分子m是吉祥数. n220090908

m11证明:由=1++L+ n220090908

1111?1??1???=?++++L++??????120090908??220090907??1004545410045455?

200909092009090920090909=++L+ 1×200909082×2009090710045454×10045455

p=20090909×,1×2××20090907×20090908

15

其中p为正整数,有

20090909×n×p=1×2×L×20090907×20090908×m,

这表明,20090909整除1×2×L×20090907×20090908×m,但20090909为素数,不能整除1×2×L×20090907×20090908,所以20090909整除m,得m是吉祥数.

4. 余数分类法.

例21 试证3n(n+1)(2n+1).

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

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,L,a+k?1,

16

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

a+i,a+j,0<i?j<k ,

使 a+i=kq1+r,

a+j=kq2+r,

其中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,L,n+k?1,

(1)若这k个连续整数为正整数,则

n(n+1)(n+2)(n+k?1)n!=k!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个连续整数为负整数,则

17

n(n+1)(n+2)(n+k?1)

k!

k(?n)(?n?1)(?n?2)(?n?k+1) =(?1)k!

=(?1)

由(1)知kCk?n,n(n+1)(n+2)L(n+k?1)为整数. k!Ck为整数,故?n

例24 有男孩、女孩共n个围坐在一个圆周上(n≥3),若顺序相邻的3人中恰有一个男孩的有a组,顺序相邻的3人中恰有一个女孩的有b组,求证3a?b.

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

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

??1, ai表示女孩时

则“3人组”数值化为

Ai=ai+ai+1+ai+2?3, ai,ai+1,ai+2均为男孩???3, ai,ai+1,ai+2均为女孩 =? aaa1,,,恰有一个女孩ii+1i+2???1, a,a,a恰有一个男孩ii+1i+2?

其中an+j=aj.

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

3(a1+a2+…+an)=(a1+a2+a3)+(a2+a3+a4)+…+(an+a1+a2) =3p+(?3)q+(?1)a+b=3(p?q)+(b?a),

可见3a?b.

例25 (1956,中国北京)证明n+

除时余2.

分析 只需说明3321n+n?1对任何正整数n都是整数,并且用322n(3n?1)321n+n=为整数,但不便说明“用3除时余2”,应说明222

n(n+1)(2n+1)31n3+n2+n=是3的倍数.作变形 222

18

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

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整除;得n+3321n+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+L+1≡14≡2(mod4),

所以,S≠0.

例27 设多项式f(x)=a0x+a1xnn?1+L+an?1x+an的系数都是整数,并且有一个

奇数α及一个偶数β使得f(α)及f(β)都是奇数,求证方程f(x)=0没有整数根.

证明 由已知有

19

f(α)≡1(mod2)?a0+a1+a2+L+an≡1(mod2), ①

f(β)≡1(mod2)?an≡1(mod2), ②

若方程f(x)=0存在整数根x0,即f(x0)=0.

当x0为奇数时,有

f(x0)≡0(mod2)?a0+a1+a2+L+an≡0(mod2),

与①矛盾.

有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+7t.?y0=2,

方法总结:第1步,验证(a,b)c,经常是(a,b)=1.

第2步,求特解(观察、列举、辗转相除等).

第3步,代入公式.

解法2 由(7,19)=1知方程有整数解.

用辗转相除法求特解,再得通解.先求

7x+19y=1

20

的一个解,由

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)

同乘以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,L,tn,那么方程的系数越来越小;对(a,b)=1,经过有限次操作,最后方程的两个未知数中必有一个系数为1,从而得到

tn?1=dtn+e,(d,e为整数)

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

21

解法4 用同余法,由7x+19y=213有

19y≡213≡3≡38(mod7) ,

但(7,19)=1,有

y≡2(mod7),

得 y=2+7t,

进而 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,有 ??? ??x+2y=2009,?y=1004,?y=1005,

?x2=72,?x=7,?x=?7,? ???y17,y24.==??x+2y=41,?

例30 甲乙两队各出7名队员按事先排好的顺序出场参加围棋擂台赛,双方先由1号队员比赛,负者被淘汰,胜者再与负方2号队员比赛,…直到有一方队员全被淘汰为止,另

(1988,一方获得胜利,形成一种比赛过程,那么所有可能出现的比赛过程的种数为 .

高中联赛)

解法1 设甲、乙两队的队员按出场顺序分别为A1,A2,A3,A4,A5,A6,A7和B1,B2,B3,B4,B5,B6,B7.如果甲方获胜,设Ai获胜的场数是xi,则0≤xi≤7,1≤i≤7而且

x1+x2+L+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, 22

问题等价于方程

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,A7和7666B1,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长可重组合是77{A1,A1,A4,A5,A5,A5,A6},所以甲方获胜的不同的比赛过程的总数就是集合

7. {A1,A2,…,A7}的7长可重组合的个数C77+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,

23

于是a1,a2,a3的取法数就是不定方程

x1+x2+x3+x4=7

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

问题又等价于不定方程

y1+y2+y3+y4=11

的正整数解.由

1+1+L+1=11,

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

七.数论函数

主要是[x]高斯函数,?(n)欧拉函数.

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

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

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

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

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

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

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

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

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

24

1~365

366~731

732~1097

1098~1463

1464~1829

1830~2004 0 1 2 3 4 5 365个 366个 366个 366个 366个 175个

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

?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!=2132537411513617719823929g31g37g41g43g47

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的倍数,则

25

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

有 4m=x=z?y=(2q+1)?(2p+1)=4q+q?p?p 22222222()

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

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

再用三边之和给小三角形赋值:当三角形的三顶点同色时,和值为0,记这样的小三角形有a个;当三角形的三顶点中仅有两点同色时,和值为2,记这样的小三角形有b个;当 26

三角形的三顶点两两异色时,和值为3,记这样的小三角形有c个.下面用两种方法计算所有三角形赋值的总和S,一方面

S=0×a+2×b+3×c=2b+3c. ①

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

S=2k+1 ②

由①,②得

2k+1=2b+3c

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

证明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,L,9同红色,下面证明,必存在一个同红色的VAiAjAk(1≤i≠j≠k≤9),其重心?xi+xj+xkyi+yj+yk,?33???也是整点.

?

(1)若A1,A2,L,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),

则VAiAjAk重心也是整点.

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

27

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

x1≡x2≡x3≡0(mod3),

x4≡x5≡x6≡1(mod3).

这时,若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),

?α+β+γ≡0(mod3),?且使 yi+yj+yk≡?α+α+α≡0(mod3),

??β+β+β≡0(mod3),

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

28

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