高二数学竞赛班二试讲义

高数竞班试义第讲同与余班一、知点金．同余

姓两个整数

,

除以正整数

，若余数相同，则称

与

b

关于模

同余，记作．性质

a)

，这叫做同余式。以下性质均在整数范围内讨论，模为正整数。（1若

m)

，则当

)

时，

a)

；则当

m)

时，

a

d

。（2若

，

m)2

，且

(m,)

，则

mm)12

。（3费尔马小定理：p为数，对任意正整数a，有|a

。费尔马小定理的推论：设

p

为素数，

为正整数，且

(,p)

，

)

。证明：由于

2,

模

p

的余数各不相同，否则，若有

iajap

，其中1jp

，则

|j

，而

不整除

，所以

(j)

，这是不可能的，因此2,

模

p

的余数必然取遍

,2,

这

个数，仅可能顺序不同。故

。又为数，则

((p1)!,)

，所以由性质（1）得

p

p)

。．剩余类设m*把全体整数按对模m的数进行类，余数为

r(0m

的所有整数归为一类，记为k，k称模的个剩余类r0,1,2,rr显然，是个以为公的无穷等差数集。它有如下性质：r（1Zkk意nZ有唯一的r使得mij。（3对任意a,Z，abka)r．完全剩余系

k

r

。设Z模的部剩余类，从每个k任一个数，rr这个a成的一个数组称为模的个完全剩余系，简称完系。m的最小非负完系。二、例分析例1）证：

是正奇数时，

n

能被

60

整除。（）

是自然数，它不能被7

整除，求证：

n8

与

n

中有且只有一个数被

整除。

10410104104104例2．,,,2,3,4,。111211求证：ab,a,至少有两个被11除得余数相同。2lm例3．设三角形的三边长分别是整数lm，l。知其中形周长的最小值。

，

三、同检测．计算

个

的乘积，则其最后三位数是（）A125B．C．

D．

．被除余数是。．求证：

(

)(n

为任意整数)。．求证：

82i

i

．两个1992

m与n

的末三位数字完全相同，试求出正整数

,n()

，使得

取得最小值。．偶数个人围着一张圆桌讨论，休息后，他们依不同次序重新围着圆桌坐下。求证至少有两个人，他们之间的人数在休息前与休息后是相同的。

第讲同与余答二、例分析例1）n是然数时，

n

n

)(a

n

n

n

)

，当n是奇数时，

n

n

)(a

n

n

n

)

，由于

n

n

n

)

n

，所以

3|

，类似

nnn

，所以

|nn

n

n

n

n

)

，所以

5|

，因为

60，两互素，故

|6

n

（2由7是数，不被17整除则

n,17)

。由费尔马小定理，得

，即

n16

，则

(

，故

0(mod17)

或

但是，

(

n

不能被17整除，所以nn中且只有一个数被7整。例2反法假设ab,ab,的余数两两不同则这些余数等于…21111这11个值，为方便起见，不失一般性，可设a被11除余数为0令kab我用两种方法计算k被11除余数。2一方面，这个余数等于1除的余数，10(mod11)另一方面

k

的任一因子都不能被11除

k

的因子中要两次遇到1～中每数，也就是

k

。矛盾！故

b1211

中至少有两个被除得的余数相同。例3．由题意

ll33]]]444410

，于是

3lm)

，即

lm4)

①且

ln)

②因为，①可知

4lm(3l

，故4|l

，所以有

3l

m

)

。注意到

4),329(mod2),334),344)

，所以

，

，同理，可由②推出

31(mod5

，故

3)

。下面求满足

3

)

的正整数k。因为

k

)

，即

5

4

k(k(22

5

4

)则

5k(k7]

k(2)3

4)所以

kt,tN

，代入上式得

7t7)

，所以

25|t

，所以

t25

，所以

故

，

为正整数，同可证

lr

，

r

为正整数，所以三角形的三边分别为

,500s,500500r由

n(500s)s500r，得r，n500r(500)sr)2000r当

srn501

时三角形周长最小，其值为3003

75327532三、同检测．A提示：

27

5(mod8)，然55

，

m1255(mod8)，所以m则

125(8k125(mod1000)

，所以最后三位数是。．7提：因为29素数，且，以

，20001996

199612．令f(nn，f(n)n,fn),n,f()1211都是f(n的式是由费尔马小定理可知13|f(nf(nf),3|f(n|f()

，又

2

两两互素，且

1

，所以

()

。．1992的质因数分解式为

3

，8282!821111记Mii238182ii因为1指是82828282[]]]]]]7028163264又因为1指是

，所以

8282!ii82828282![]]]]40，以32781ii1下面证明83|M。考虑证明当ij时(mod83)ij

。不妨设

j82

，则由

是素数得

3|j,83|

，因而

83|82!

ji

，所以

1182!(mod83)，且0(mod83)iji

，所以

11,82!1282

模的数两两不同，且取遍,2,从而推得又8,3,83

8282!M，Mii两两互素，故8M，M．

m1992n(1992

，而

3249,1000

，可取由

25|1992

m

，1

m

故有

(m1(mod5)

，则

(m1(mod5)

，所以

k(N)

，因此

(mk又

(1004)

，则

m

1

，即

(

k

(1)

，所以

(

k25k或(k

k

（不可能）所以

kh

，从而

1

5h

h

，由二项式定理知，

(

h25)]

由此的最小值为5于是

100，所以

．用反证法证明。将每位的号码依顺时针记为

，每一个人对应一个二元有序整数组

(ij)

。其中ij

为他休息前后的座号全体人员