2013高中数学奥数培训资料之同余

兰州成功私立中学高中奥数辅导资料
（内部资料）
§27同余
1．设m是一个给定的正整数，如果两个整数a与b用m除所得的余数相同，则称a
与b对模同 余，记作
a?b(modm)
，否则，就说a与b对模m不同余，记作
a?b(mod m)
，显然，
a?b(modm)?a?km?b,(k?Z)?m|(a?b)
；
每一个整数a恰与1，2，……，m，这m个数中的某一个同余；
2.同余的性质：
1).反身性：
a?a(modm)
；
2).对称性：
a?b(modm)?b?a(modm)
；
3).若a?b(modm)
，
b?c(modm)
则
a?c(modm)
;
4).若
a
1
?b
1
(modm)
，
a
2
?b
2
(modm)
，则
a
1
?a
2
?b
1
?b
2
(modm)

特别是
a?b(modm)?a?k?b?k(modm)
；
5).若
a< br>1
?b
1
(modm)
，
a
2
?b
2
(modm)
，则
a
1
a
2
?b
1b
2
(modm)
；
特别是
a?b(modm),k?Z?则ak?bk(modm)


a?b(modm),n?N?则a?b(modm)
；
6).
a(b?c)?ab?ac(modm)
；
7).若
ac?bc(modm),则当(c,m)?1时，a?b(modm)


当(c,m)?d时，a?b(mod
8).若
a?b(modm1
)
，
a?b(modm
2
)

a?b(modm
3
)

m
d
).特别地，ac?bc(modmc)?a?b(modm)
；
nn
………………
m
n
)
，且
M?[m1
,m
2
,??m
n
]，则a?b(modM)

a?b(mod

例题讲解
1．证明：完全平方数模4同余于0或1；
2．证明对于任何整数
k?0
,
2
6k?1
?3
6k?1
?5
6k
?1
能 被7整除；


3．试判断
1971


4．能 否把1，2，……，1980这1980个数分成四组，令每组数之和为
S
1
，S2
，S
3
，S
4
，
且满足
S
2?S
1
，＝10，S
3
?S
2
＝10，S
4< br>?S
3
＝10；



5．在已知数列1，4，8， 10，16，19，21，25，30，43中，相邻若干数之和，能被11整除
的数组共有多少组。


nn?1n?21
?a
2
x???a
n?1< br>x?a
n
是整系数多项式， 6．设
f(x)?a
0
x?a< br>1
x
26
?1972
27
?1973
28
能 被3整除吗？
证明：若
f(0),f(1),?,f(1992)都不能被1992整除，则 f(x)没有整数根；



7．试求出一切可使
n?2?1
被3整除的自然数
n
；
n


8．在每张卡片上各写出11111到99999的五位数，然后把这 些卡片按任意顺序排成一列，
证明所得到的444445位数不可能是2的幂；


9．设
a
1
,a
2
,?a
n
,?
是任意一个具有性质
a
k
?a
k?1
,(k?1)
的正整数 的无穷数列，求证可

以把这个数列的无穷多个
a
m
用适当的正整数
x,y表示为a
m
?x?a
p
?y?a< br>q
,(p?q)

课后练习
1、证明：完全平方数模3同余于0或1；
证明：完全平方数模5同余于0、1或4；
证明：完全平方数模8同余于0、1或4；
证明：完全立方数模9同余于-1、0或1；
证明：整数的四次幂模16同余于0或1； < br>2、设
a?Z，且(a,10)?1，求a
20
(在十进制中)的末两位数码；






3、
求2
999
最后两位数码






4.有一个120位的数，将它的
得到的120位数中随意挑出
12位数码以一切可能的方
120个数来，证明它们的和
式重新排列，然后从按
可以被 120整除；
这种方法所



5.连接写出19到80的两位数， 问：所得到的数：192021?7980能被1980整除吗？

课后练习答案
1.略
2.解：
?
(a,10)?1，?a为奇数
?a
20
?a
2
?
(25)
?1(mod25)
20

又
?
a
20
20
?1(mod4)?a?1(mod4)

又
?
(25,4)?1
?a?1(mod100)
01
999
?a的末 两位位
3.解 考虑用100除2所得的余数.
∵∴
又，∴
∴

∴2
999
的最后两位数字为88.

3.证：设这12 0个120位数的前12个数码分别组成的数为
而每一数的剩下的108个数码组成了数
108
：A
1
,A
2
,
?
A
120
B， 则这120个数的和为：
S＝(A
1
?A
2
?
?
? A
120
)?10
考虑到40|10
108
?120B
，且 A
1
,A
2
,
?
A
120
每个被3除时余 数相同
108

?3|A
1
?A
2
?
?< br>?A
120
,又
?
(3,40)?1?120|(A
1
?A
2
?
?
?A
120
)?10
?120|S< br>5.解：设A＝192021
?
7980，显然20|A
又
?
100
k
?(99?1)?99M?1?100
61
kk
?1(mo d99)
?
A?19?100?20?100
60
?
?
?7 9?100?80?(19?20?21?
?
?79?80)(mod99)
?A?3 1?99(mod99)?0(mod99)
?99|A
又
?
(20,99) ?1
?1980|A

例题答案：
1．证明：
设n是任一整数，则n?2k或者n?2k?1,k?Z;

2

当n?2k时，n
2
?4k
2
?0(mod4 );
当n?2k?1时，n
2
?（2k?1)?1(mod4);

所以原命题成立；

2.证：令M?2
?M?2?2
6k
6k?1
?3
6k
6k?1
6k
?5
6k
?1
?3?3
k
?5
k
?1
k
?2?64?3? 729
k
?15625?1
kk
?2?(7?9?1)?3?(7?104? 1)?(7?2232?1)?1
?2?7?A?2?3?7?B?3?7?C?1?1
?(2 ?3?1?1)(mod7)?0(mod7)

?对于?k?0,且k?Z,
26k?1
?3
6k?1
?5
6k
?1
都能被7整除；
注：
a?1(modb)?a
k
?1(modb),k?Z
?

3.解：
?
1971?0(mod3),1972?1(mod3),1973? 2(mod3)
?1971
26
26
?1972
?1972
?4
14
27
27
?1973
28
28
?(026
?1
27
?2
28
)(mod3)
即：1971< br>又
?
2
?1971
?1973?(1?2
28
28< br>)(mod3)

28
26
?1(mod3),?(1?2
2 7
)?2(mod3)
?1972?1973
28
不能被3整除；
4 .解：依题意可知：T?S
1
?S
2
?S
3
?S
4
＝S
1
?S
1
?10?S
1
?20?S
1
?30
1980?1981
2
?T?4S
1
?60?0(m od4)
又
?T
?1?2?3?
?
?1980?
?产生矛盾 ，?不能这样分组；
5.解：记数列各对应项为a
i
,i?1,2,
?
10，并记S
k
?a
1
?a
2
?
?
?a
k
?990?1981?2(mod4)

?S
1
,S2
,
?
,S
10
依次为1、5，13、23、39、58、79 、104、134、177
它们被11除的余数依次为：1、5、2、1、6、3、2、5、2、1由此可得：S
1
?S
4
(mod11)?S
10
(mo d11),S
2
?S
8
(mod11),S
3
?S
7
(mod11)?S
9
(mod11)
S
k
?S
j
(mod11)时，由于S
k
?S
j
是数列{a
i
}相邻项之和，且当
11|S
k
?S
j
，则满足条件的数组有：3 ?1?3?7组

6.证：假设f(x)有整数根m，且 m?r(mod1992),0?r?1992
由题意f(r)不能被1992整除，
?
f(m)?0,则f(r)?f(m)?f(r)
又
?
f(r)?f(m)?a0
(r?m)?a
1
(r
?
m?r(mod1992)
?m?r(mod1992),i?1、2、3、
?
、n
?m?r?0(mod199 2),i?1、2、3、
?
、n
?1992|f(r)?f(m)?f(r)
?产生矛盾，?f(x)没有整数根
7.解：若3|n?2?1，则n?2
考虑到n及2，则< br>当n?6k?1时，(k?0、1、2、
?
)
n?2?(6k?1)?2
n6k?1
n
nn
nnn?1
?m
n?1
)?
?
?a
n?1
(r?m)

i
i
i
i
?2(mod3)
?(12k?2)?(3?1)
k
?2(mod3)
当n ?6k?2时，(k?0、1、2、
?
)
n?2?(6k?2)?2
n6k? 2
?(24k?8)?(3?1)
k
?2(mod3)
当n?6k?3时，( k?0、1、2、
?
)
n?2?(6k?3)?2
n6k?3
?0( mod3)
当n?6k?4时，(k?0、1、2、
?
)
n?2?(6k?4 )?2
n6k?4
?(96k?64)?(3?1)
k
?1(mod3)当n?6k?5时，(k?0、1、2、
?
)
n?2?(6k?5)?2
n6k?5
?(6?32k?160)?(3?1)
k
?1(mod3)
当n ?6k?6时，(k?0、1、2、
?
)
n?2?(6k?6)?2
由上可知 当且仅当
n6k?6
?0(mod3)
n
n?6k?1，6k?2时，n?2 能被3整除；
A，则：

8.证：记由11111、11112、
??
、99999排成的数为
A＝a
1
a
2
??
a
8 8889
,a
i
?{11111、11112、
??
、99999}
?A＝a
1
?10
注意到10
5
444440
?a
2
?10
444435
?a
3
?10
5k
444430
?
?
?a
88888
?10
5
?a< br>88889
?1(mod11111)?10?1(mod11111),k?Z
?A? a
1
?a
2
?
?
?a
88888
?a88889
(mod11111)
又
?
a
1
?a
2
?
?
?a
88888
?a
88889
?111 11?11112?
?
?99999?
即：a
1
?a
2?
?
?a
88888
?a
88889
?11111?5 ?88889
?A?0(mod11111)
?A不可能是2的幂；
11111?99 999
2
?88889

9.证：将{ a
n
}按a
2
为模的不同剩余类分成
?
{a
n}为无限集，而子数列却
?至少有一个子数列有无
现考虑这个无穷数列
又
?
{a
n
}为严格递增的
?该子数列中必有一个最
是有限多个
若干个子数列
穷多项
小的a
p
,a
p
?a
2，同时还有无限多个a
m
属于该子数列，且a
m
?a
p
?
a
m
?a
p
(moda
2
)?a
m?a
p
?xa
2
,x?Z
令y＝1，a
q
?a
2
?a
m
?ya
?a
m
是满足题意的要求，且p
?xa
q
a
m
是无限多个