包头市数学联赛辅导 复赛数论初步选讲----------北重三中 樊增平
第二讲 同余
一.基础知识
1.定义1. 设m是正整数，若用m去除整数a,b，所得的余数相同，则称a与b关于模m同余，记作
a?b(modm)，否则称a与b关于模m不同余，记作a1000??1(mod7)，98(mod2) 等等。
b(modm).例如：34?4(mod15)，
当0?b?m时，a?b(modm)，则称b是a对模m的最小非负剩余。 对于固定的模m，通常有下面的性质：
性质1. a?b(modm)的充要条件是a?mt?b,t?Z也即m|(a?b)。 性质2.同余关系满足以下规律： （1）（反身性）a?a(modm)；
（2）（对称性）若a?b(modm)，则b?a(modm)；
（3）（传递性）若a?b(modm)，b?c(modm)，则a?c(modm)；
（4）（同余式相加）若a?b(modm)，c?d(modm)，则a?c?b?d(modm)； （5）（同余式相乘）若a?b(modm)，c?d(modm)，则ac?bd(modm)；
注意：① 反复利用（4）（5），可以对多于两个的（模相同的）同余式建立加、减和乘法的运算公式 ；
kk② 特别地，由（5）易推出：若a?b(modm)，k,c为整数且k?0，则ac?bc(modm)；
③ 同余式的消去律一般并不成立，即从ac?bc(modm)未必能推出a?b(modm)，可是我们却有
以下结果：若ac?bc(modm)，则a?b??mod??m??. ?(m,c)?由此可以推出：
（6）若(c,m)?1,ac?bc(modm)，则有a?b(modm)，即在c与m互素时，可以在原同余式两边约去c而不改变模.
（7）若a?b(modm)，d｜m，则a?b(modd)； （8）若a?b(modm)，d?0，则da?db(moddm)；
（9）若a?b(modmi)(i?1,2,?,k)，则a?b(mod[m1,m2,?,mk])，
特别地，若m1,m2,?,mk两两互素时，则有a?b(modm1?m2???mk)；
1
包头市数学联赛辅导 复赛数论初步选讲----------北重三中 樊增平
kkkk性质3.若ai?bi(modm),i?1,2,?,k，则
?a??b(modm)；?a??b(modm)；
iiiii?1i?1i?1i?1性质4.设f(x)是系数全为整数的多项式，若a?b(modm)，则f(a)?f(b)(modm)。
这一性质在计算时特别有用：在计算大数字的式子时，可以改变成与它同余的小数字，使计算大大地简化。
整数集合可以按模m来分类，确切地说，若a和b模m同余，则a和b属同一类，否则不属于同一类，每一个这样的类称为模m的一个同余类。由带余除法，任一整数必恰与0,1,……，m?1中的一个模m同余，而0,1,……，m?1这m个数彼此模m不同余，因此模m共有m个不同的同余类， 例如，模2的同余类共有两个，即通常说的偶数类与奇数类，这两类中的数分别具有形式2k和2k?1（k为任意整数）. 2. 定义2 （剩余类）设m是正整数，把全体整数按对模m的余数分成m类，相应的m个集合记为：，K0,K1,?,Km?1，其中每一个Kr?{x|x?qm?r,q?Z}称为模m的一个剩余类（也称同余类）
r?0,1,?,m?1.
3. 定义3.（完全剩余系）
设K0,K1,?,Km?1为模m的全部剩余类，从每个Kr中任取一个元素ar，得m个数a0,a1,?,am?1组成的数组，叫做模m的一个完全剩余系.
例如：关于模7，下面的每一组数都是一个完全剩余系：
0，1，2，3，4，5，6； -7，8，16，3，-10，40，20； -3，-2，-1，0，1，2，3。
最常用的完全剩余系是最小非负完全剩余系和绝对值最小完全剩余系. 模m的最小非负完全剩余系是：0，1，2，………,m?1; 当m为奇数时，绝对值最小的完全剩余系是：?m?1m?1,?,?1,0,1,?,； 22当m为偶数时，绝对值最小的完全剩余系有两个：
mm?1,?,?1,0,1,?,； 22mm?,?,?1,0,1,?,?1。 22?4.定义4.（简化剩余系）
在模m的完全剩余系中，由所有与m互素的数组成的数组叫做模m的简化剩余系，也称既约剩余系. 注意：简化剩余系不是完全剩余系，只是完全剩余系的一部分.
例如：0、1、2、3、4、5、6、7、8、9是模10的一个完全剩余系，1、3、7、9是模10的一个简化剩余
2
包头市数学联赛辅导 复赛数论初步选讲----------北重三中 樊增平
系，且满足?(10)=4. 5. 欧拉(Euler)函数?(n)
n个整数0,1，……，n?1中与n互素的数的个数，称之为n的欧拉函数，记为?(n).
定理1：若p是素数，则?(p?)?p??p??1. 定理2：若?m,n??1，则?(mn)???m???n?.
a1a2定理3：若n的标准分解式是n?p1p2?pkk,，则?(n)的计算公式是： ak?1a1?1a2?1 ?(n)?p1p2?pk(p1?1)(p2?1)?(pk?1)=n?aP为质数1. （1－）?PP|n例如：?(2000)??(2453)?2352(2?1)(5?1)?800；
?? ?(2001)6.几条常用的性质 （1）Z??(3?23?29?)(3?1)(2?3?1)(2. 90?i?m?1?Ki，其中Ki?Kj??，(?i?j，i,j??0,1,?,m?1?)；
（2）每一个整数只包含于K0,K1,?,Km?1中的一个里；
（3）对于任意a,b?Z，则a,b?Kr的充要条件是a?b(modm). （4）m个整数构成模m的一个完全剩余系?任意两数模m不同余；
，b?Z，则 （5）若x1,x2,?,xm是模m的一个完全剩余系，且(a,m)?1ax1?b,ax2?b,?,axm?b也是模m的一个完全剩余系；
（6）简化剩余系中数的个数为?(m) ；
，则ax1,ax2,?,ax??m?也是模m的一个简（7）若x1,x2,?,x??m?是模m的一个简化剩余系，且(a,m)?1化剩余系（其中??m?是欧拉函数）.
【例题分析】
1．试求(257?46)被50除所得的余数。 解：由于(x333326?46)26是关于x的整系数多项式，而257?7(mod50)，
26于是知 (257?46)233?(733?46)26(mod50)
33263326又注意到7=49??1(mod50)，故(257?46)?(7?46)
3
?((72)16?7?46)26
包头市数学联赛辅导 复赛数论初步选讲----------北重三中 樊增平
?((?1)16?7?46)26?(7?46)26?5326?326(mod50)
又 35?243??7(mod50)，
223326?(7)?7?3?所以 (257?46)?(35)5?3?(?7)5?3??????21?29(mod50)
注意到0?29?50，因而29就是所求的余数.
说明：在上述过程中，我们已经看到72?49??1(mod50)的作用。一般而言，知道一个整数的多少次幂关于模同余于?1是非常有用的。事实上，若ak?1(modm)，则对大的指数n利用带余除法定理，可得
n?kq?r,0?r?k，于是有an?akq?r?(ak)qar?ar(modm)，这里余数r是一个比n小得多的数，这
样一来，计算a的问题，就转化成了计算余数r次幂a的问题，从而使计算简单化。 2．设a?1010，若今天是星期一，计算第a天后是星期几？ 解；星期几的问题是被7除求余数的问题.
由于10?3(mod7)，于是103?33??1(mod7)，因而106?1(mod7)。 为了把指数a的指数10写成6q?r的形式，还需取6为模来计算10。
为此我们有：10?4(mod6)，进而有：102?42?4(mod6)，103?43?4(mod6)，…… ， 依次类推有：10?4(mod6)，所以 10?6q?4 . 从而 a?106q?41010101010nr?(106)q?104?1q?104?34?4(mod7)，所以星期一后的第a天将是星期五.
27an?45an?363．数列{an}满足：a0?1,an?1?2,n?N.证明：
（1）对任意n?N,an为正整数； (2)对任意n?N,anan?1?1为完全平方数。 证明：（1）由题设得a1?5,且{an}严格单调递增.将条件式变形得：
2222an?1?7an?45an?36,两边平方整理得an?1?7anan?1?an?9?0 ①
22?an?7an?1an?an?1?9?0 ②
①-②得(an?1?an?1)(an?1?an?1?7an)?0,?an?1?an,?an?1?an?1?7an?0?an?1?7an?an?1. ③ 由③式及a0?1,a1?5可知，对任意n?N,an为正整数. （2）将①两边配方，得(an?1?an)?9(anan?1?1),?anan?1?1?(2an?1?an2). ④ 3n由③式an?1?an?9an?(an?1?an)≡?(an?an?1)?mod3? ∴an?1?an≡(?1)
4
?a1?a0?≡0（mod 3）
包头市数学联赛辅导 复赛数论初步选讲----------北重三中 樊增平
∴
an?1?an为正整数，④式符合题意. ?anan?1?1是完全平方数. 34．求所有的素数p，使得4p2?1与6p2?1也是素数。
分析：要使几个数同为质数，一般是利用某一质数的余数来确定，如p,p?2,p?4均为质数，由于这是
p的一次式，故三个数就用模3的余数来确定，而二次式对三个数就模5，四个数一般就模7了。要使p，
4p2?1与6p2?1都是素数，须对p除以素数q?5的余数进行分类讨论，最后确定p只能是这个素数.
解：设u?4p2?1，v?6p2?1，且p?5k?r,k?Z,r?{0,1,2,3,4} 若r?1或4时，p2?1(mod5)，u?4p2?1?4?1?0(mod5)； 若r?2或3时，p2?4(mod5)，v?6p2?1?24?1?0(mod5)； 即r?0时，u,v为5的倍数且比5大，不为质数。故r?0，此时p?5，
u?52?4?1?101；v?52?6?1?151都是素数，即本题有唯一解p?5。
二、几个重要定理
定理1：（欧拉（Euler）定理）若(a,m)＝1，则a?(m)?1(modm). 证明：取模m的一个既约剩余系 b1,b2,?,bs,(s??(m)) ………………① 由性质易知：ab1,ab2,?,abs ………………②
也是模m的一个既约剩余系，于是①中的任意一个数都能在②中找到与它同余的数，反之也如此 从而
?(ab)??b(modm)， ?a(?b)?(?b)(modm)
sjjssssjjj?1j?1j?1j?1?(m,?bj)?1，?as?1(modm)，故a?(m)?1(modm)，证毕.
j?1s分析： 这是数论证明题中常用的一种方法，使用一组剩余系，然后乘一个数组组成另外一组剩余系来解决问题。
p定理2：（费尔马（Fermat）小定理）对于质数p及任意整数a有a?a(modp). p证明：设p为质数，若a是p的倍数，则a?0?a(modp).
若a不是p的倍数，则(a,p)?1，由欧拉函数的计算公式及欧拉定理得?(p)?p?1,a?(p)?1(modp)
?ap?1?1(modp),ap?a(modp)，由此定理成立.
p?1推论：设p为质数，a是与p互质的任一整数，则a?1(modp).
5