同余理论在数学竞赛中的运用
卢军萍
杭州师范大学 数学与应用数学043班
摘要：这些年来，同余理论在数学竞赛中的应用越来越广泛。本文详细了同余理论的基础知识，并通过举例以便更好的理解。并重点对数学竞赛中有关同余理论的应用作了系统的划分。每一部分都有2-4个例题加以举例说明。 关键词：同余；数学竞赛
１ 引 言
数学竞赛已逐渐形成一门特殊的数学学科——竞赛数学。像IMO竞赛等等受到越来越大的重视。而在数学竞赛中，初等数论的有关题目占得比例越来越大，尤其是同余理论在数学竞赛中有着举足轻重的地位。下面，本文重点论述一下同余理论在数学竞赛中的运用。首先，先介绍一下同余的一些基本知识。
２ 同余的性质及几个重要的定理
２.１同余的定义、性质
[定义１] 给定正整数m，如果整数a与b之差被m整除，则称a与b对于模m同余，或称a与b同余，模m，记为
a?b?modm?,
此时也称b是a对模m的同余。
如果整数a与b之差不能被m整除，则称a与b对于模m不同余。 [定理１] 下面的三个叙述是等价的： （ⅰ）a?b?modm? ；
（ⅱ）存在正整数q，使得a?b?qm, （ⅲ）存在整数q1，q2，使得a?q1m?r[定理２] 同余具有下面的性质： （ⅰ）（自反性）a?a(modm)；
（ⅱ）（对称性）若a?b(modm)，则b?a(modm)； （ⅲ）（传递性）若a?b,b?c(modm)，则a?c(modm)； （ⅳ）假设a,b,x,y是整数，并且a?b(modm),x?y(modm)，则
,a?q2m?r，0?r?m.
a?x?b?y(modm),ax?by(modm)；
1
（ⅴ）设ai,bi (0?i?n)以及x,y都是整数，并且x?y(modm)，ai?bi(modm)，
0?i?n，则
?nnaxi??biyii(modm)；
i?0i?0（ⅵ）a?b(modm),dm,d?0?a?b(modd);
（ⅶ）a?b(modm),k?0,k?N?ak?bk(modmk);
（ⅷ）若a?b(modmi)，(i?1,2,?,n)，则a?b(mod[m1,m2,?,mn]); (ⅸ)a?b(modm)?(a,m)?(b,m);
(ⅹ)ac?bc(modm),(c,m)?1?a?b(modm).
下面简单介绍一下，以上同余性质的一些应用。 [例１] 求(25733?46)26被50除的余数。 解： 有性质（ⅴ）得， (25733?46)26??733?4?26??7?72?16?4?26
??7??1?16?4?26??7?4?26
?326?3?35?5 ?3??7?5??3?7??72?2
??21???1?2??21
?29?mod50?
即所求的余数是29。 [例２] 求n?777的个位数。
解： 因为71??3,72??1,74?1?mod10?
因此若77?r?mod4?
则 n?777?7r?mod10? （１）
现在77?(?1)7??1?3?mod4?
所以由式（1）得到
2
n?77?73???3???7?3?mod10?,
73即n的个位数是3。
[例３] 证明：若n是正整数，则13|42n?1?3n?2。11 证明：因为42n?1?3n?2?4?42n?9?3n?4?16n?9?3n
再有性质（ⅵ）得，
4?16n?9?3n?4?3n?9?3n?13?3n?0?mod13?
得证。
[例４] 已知99|62??427,求?和?。 解：因为99=9?11
所以9|62??427, （２）
11|62??427, （３）
有（２）式得：9|6?2?????4?2?7?21????
?9|3???? （４）
有（３）式得：11|6?2?????4?2?7?13????
?11|2???? （５）
由于0??,??9，所以由式（４）与（５）得出
????15或6，????9或?2，可得四个方程组 ?????6?????6?????15?????15或?或?或??????9?????2????9?????????2 ，
解得??2，??4。
２.２剩余类、完全剩余系和简化剩余系
[定义２]给定正整数m，对于每个整数i，0?i?m?1,称集合
Ri(m)??n|n?i(modm),n?Z?
是模的一个剩余类。
[定义３]设m是正整数，从模m的每一个剩余类中任取一个整数xi(0?i?m?1)，称集合?x0,x1,?,xm?1?是模的一个完全剩余系（或简称为完全系）。
3
由于xi的选取是任意的，所以模m的完全剩余系有无穷多个，通常称： i. ii.
?0,1,2,?,m?1?是模m的最小非负完全剩余系；?1?1??m??(当m是奇数时),?,?1,0,1,?,m)或?－m2,?,?1,0,1,?,m22?12(当m是偶数时是模的绝对最小的完全剩余系。
［定理３］整数集合A是模m的完全剩余系的充要条件是：
i. A中含有m个整数； ii. A中任何两个整数对模m不同余。
[定理４］设m?1,a,b是整数（a,m）?1,{x1,x2,?,xm}是模m的一个完全剩余系，则?a1x1?b,a2x2?b,?anxn1?b?也是模m的一个完全剩余系。
［定理５］设m1,m2?N,A?Z,(A,m)?1, X?{x1,x2?xn},Y?{y1,y2?yn} 分别是模m1和模m2的完全剩余系，则R?{Ax?m1y|x?X,y?Y}是模m1,m2的一个完全剩余系。
［推论１］若m1,m2?N,(m1,m2)?1，则当x1和x2分别通过模m1和模m2的完全剩余系数时，m2x1?m1x2通过模m1,m2的完全剩余系数。
［定理６］设mi?N(1?i?n)，则当xi通过模mi(1?i?n)的完全剩余系数时，
x?x1?m1x2?m1m2x3???m1m2?mi?1xn通过模m1m2?mn的完全剩余系数。
［定义４］设Ｒ是模m的一个剩余类，若有a?R,使得(a,m)?1，则称Ｒ是模m的一个简化剩余类。
［例５］设p?5是素数，a?{2，3?p?2}，则在数列
a,2a,3a,?(p?1)a,pa （６）
中有且仅有一个数b，满足：
b?1(mod p) (７)
若b?ka则k?a,k?{2,3,?p?2}。
解：因为（a，p）=1, 所以由定理２，式（６）中的数构成模p的一个完全剩余类，因此，必有数b满足试（７），设b=ka，那么 i.
k?p,否则b?pa?0(modp)与b?1(modp)；
4
