高中数学竞赛讲座之同余
【知识点】
1．设m 是一个给定的正整数，如果两个整数a 与b 用m 除所得的余数相同，则称a
与b 对模同余，记作)(mod m b a ≡，否则，就说a 与b 对模m 不同余，记作
)(mod m b a ≡，显然，)(|)(,)(mod b a m Z k b km a m b a -⇔∈+=⇔≡；
每一个整数a 恰与1，2，……，m ，这m 个数中的某一个同余；
2.同余的性质：
1).反身性：)(mod m a a ≡；
2).对称性：)(mod )(mod m a b m b a ≡⇔≡；
3).若)(mod m b a ≡，)(mod m c b ≡则)(mod m c a ≡;
4).若)(m od 11m b a ≡，)(m od 22m b a ≡，则)(m od 2121m b b a a ±≡±
特别是)(mod )(mod m k b k a m b a ±≡±⇔≡；
5).若)(m od 11m b a ≡，)(m od 22m b a ≡，则)(m od 2121m b b a a ≡；
特别是)(m od ),(m od m bk ak Z k m b a ≡⇔∈≡则
)(m od ),(m od m b a N n m b a n n ≡⇔∈≡则；
6).)(mod )(m ac ab c b a +≡+；
7).若)(m od 1),(),(m od m b a m c m bc ac ≡=≡时，则当
)(mod )(mod ).(mod
),(m b a mc bc ac d
m b a d m c ≡⇔≡≡=特别地，时，当； 8).若)(m od 1m b a ≡， )(m od 2m b a ≡
)(mod 3m b a ≡
………………
)(mod n m b a ≡，且)(m od ],,[21M b a m m m M n ≡⋯⋯=，则
【例1】证明：完全平方数模4同余于0或1；
证明：;,122Z k k n k n n ∈+==或者是任一整数，则设
);4(m od 04222≡==k n k n 时，当);4(m od 1)121222≡+=
+=k n k n （时，当 所以原命题成立；
【例2】证明对于任何整数0≥k ,153261616+++++k k k 能被7整除；
1533221
53266661616++⋅+⋅=∴+++=++k k k k k k M M 证：令
)
7(mod 0)7)(mod 1132(1
173732721)122327()11047(3)197(21
156257293642=+++=++⋅++⋅⋅++⋅⋅=++⋅++⋅⋅++⋅⋅=++⋅+⋅=C B A k k k k k k ,,0Z k k ∈≥∀∴且对于153261616+++++k k k 都能被7整除；
注：+∈≡⇒≡Z k b a b a k ),(m od 1)(m od 1
【例3】试判断282726197319721971++能被3整除吗？
整除；
不能被又即：解：3197319721971)
3(mod 2)21(),3(mod 142)
3)(mod 21(197319721971)
3)(mod 210(197319721971)
3(mod 21973),3(mod 11972),3(mod 0197128272628142828282726282726282726++∴≡+∴≡=+≡++++≡++∴≡≡≡
【例4】能否把1，2，……，1980这1980个数分成四组，令每组数之和为4321S S S S ，，，， 且满足；＝，＝，，＝101010342312S S S S S S ---
不能这样分组；
产生矛盾，又＝解：依题意可知：∴∴≡⋅=⋅=++++=≡+=∴+++++++++=)4(mod 219819902
198119801980321)
4(mod 060430
2010111114321 T S T S S S S S S S S T
【例5】在已知数列1，4，8，10，16，19，21，25，30，43中，相邻若干数之和，能被11整除的数组共有多少组。
组
：，则满足条件的数组有时，
相邻项之和，且当是数列由于由此可得：、、、、、、、、、除的余数依次为：它们被、、、、、、、，、依次为，并记解：记数列各对应项为7313|11)11(mod }{)11(mod )11(mod ),11(mod ),11(mod )11(mod 1
25236125111177
134104795839231351,,,10,2,1,973821041102121=++-≡-≡≡≡≡≡∴+++==j k j k i j k k
k i S S S S a S S S S S S S S S S S S S a a a S i a 【例6】设n n n n n a x a x
a x a x a x f +++++=---1122110)( 是整系数多项式， 证明：若没有整数根；整除，则都不能被)(1992)1992(,),1(),0(x f f f f
没有整数根
产生矛盾，、、、、、、、、又则整除，
不能被由题意，且有整数根证：假设)()
()()(|1992321),1992(mod 0321),1992(mod )
1992(mod )
()()()()()
()()(,0)(1992)(1992
0),1992(mod )(11110x f r f m f r f n
i r m n
i r m r m m r a m r a m r a m f r f r f m f r f m f r f r r m m x f i i i i n n n n n ∴∴=-∴=≡-∴=≡∴≡-++-+-=-=-=<≤≡---
【例7】试求出一切可使12+⋅n n 被3整除的自然数n ；
