（2）每一个整数仅在K0,K1,?,Km?1的一个里； （3）对于任意a,b?Z，则a,b?Kr的充要条件是a定义5.（完全剩余系）一组数
?b(modm)。
的完全剩余系，如果对任意a有且仅有一个
y1,y2,?,ys称为模myj是a对模m的剩余，即
a?yj(modm)。换一种说法更好理解：
设K0,K1,?,Km?1为模m的全部剩余类，从每个Kr中任取一个ar，得m个数a0,a1,?,am?1组成的数组，叫做模m的一个完全剩余系。
说明：在m个剩余类中各任取一个数作为代表，这样的m个数称为模m的一个完全剩余系，简称模m的完系。换句话说，m个数
c1,c2,?,cm称为模m的一个完系，是指它们彼此模m不同余，例如0,1，2，……，m?1是模m的一个完系，这称作是模m的最小
非负完系。
性质：（1）m个整数构成模m的一个完全剩余系?两两对模不同余；
（2）若(a,m)典例分析 例1．试解方程：
?1，则x与ax?b同时跑遍模m的完全剩余系。
?5?6x?15x?7?。
??5?8?解：因为左边是整数，因而右边的分式也应该是整数，所以
15x?7?5?6x??5?6x15x?7???????0
???8558????于是
81?90x?81?90x??0，从而0??1，故0?81?90x?40。
??40?40?，直接观察即知t但是
15x?7是整数，故15x?5t?7，t?Z，代入前面的不等式，得0?39?30t?40,t?Z574x?,。
155?0,1，于是
例2．数100！的十进位制表示中，未尾连续地有多少位全是零？
解：命题等价于100！最多可以被10的多少次方整除。因为10?2?5因而100！中2的指数大于5的指数，所以100！中5的指数就是所需求出的零的位数。 由??100??100?????2??20?4?24即可知100！的未尾连续地有24位全是数码零。
?5???5?33例3．试求(257解：由于(x33?46)26被50除所得的余数。
?46)26是关于x的整系数多项式，而257?7(mod50)，于是知
(25733?46)26?(733?46)26(mod50)。
又注意到72?49??1(mod50)，故(25733?46)26?(733?46)26(mod50)?((72)16?7?46)26
?((?1)16?7?46)26?(7?46)26?5326?326(mod50)
又35?243?250?7??7(mod50)，所以(25733?46)26?(35)5?3?(?7)5?3
??(72)2?7?3??21?29(mod50)
注意到0?29?50，因而29就是所求的余数。
说明：在上述过程中，我们已经看到7用的。事实上，若
2?49??1(mod50)的作用。一般而言，知道一个整数的多少次幂关于模同余于?1是非常有
，则对大的指数
ak?1(modm)n利用带余除法定理，可得
n?kq?r,0?r?k，于是有
an?akq?r?(ak)qar?ar(momd)，这里余数r是一个比n小得多的数，这样一来，计算an的问题，就转化成了计算余数r次幂
ar的问题，从而使计算简单化。
例4．设a?101010，计算某星期一后的第a天是6星期几？
2解；星期几的问题是被7除求余数的问题。由于10?3(mod7)，于是10?32?2(mod7)，
103?33?2?3?6??1(mod7)，因而106?1(mod7)。
为了把指数a的指数1010写成6q?r的形式，还需取6为模来计算1010。为此我们有
，依次类推，有
10?4(mod6)，进而有
102?42?4(mo6d)，
103?43?4(mod6)1010?4(mod6)，所以
1010?6q?4(mod6)
从而，a?106q?4?(106)q?104?1q?104?34?4(mod7)
这样，星期一后的第a天将是星期五。 例5．求所有的素数分析：要使4p2p，使4p2?1与6p2?1也是素数。
?1与6p2?1也是素数，应该是对p除以某个数素q的余数进行分类讨论，最后确定p只能是这个素数。由于只有
两个数，所以q不能太大，那样讨论起来也不会有什么效果，试验q解：设u若r若r即r?2,3发现对本题不起任何效果，现对q?5展开讨论。
?4p2?1，v?6p2?1，且p?5k?1,k?Z,r?{0,1,2,3,4}
?1或4时，p2?1(mod5)，u?4p2?1?4?1?0(mod5)； ?2或3时，p2?4(mod5)，v?6p2?1?24?1?0(mod5)； ?0时，u,v为5的倍数且比5大，不为质数。故r?0，此时p?5，
u?52?4?1?101；v?52?6?1?151都是素数。
即可题有唯一解
p?5。
p,p?2,p?4均为质数，可得p只能为3，由于这
注：要使几个数同为质数，一般是对这几个数也合乎以某一质数的余数来确定，如是
p的一次式，故三个数就模3，而二次式对三个数就模5，四个数一般就模7了。
m例6．求满足|12分析：如果5n?5n|?7的全部正整数m,n。
?12m?7，两边mod4，得1?3(mod4)，这是不可能的；
m 如果12得?5n?5n?7，而m,n中有一个大于1，则另一个也大于1，mod3得?(?1)n?1(mod3)，故n为奇数，mod8，
??1(mod8)，而52?1(mod8)，n为奇数，从而?5??1(mod8)，矛盾！
所以m?n?1为唯一解。
注：在解不定方程时，往往要分情况讨论，也常常利用同余来导出一些性质求出矛盾！
例7．数列{an}满足：a0?1,an?1?27an?45an?362,n?N.
?1为完全平方数。
（2005年全国高中数学联赛试题）
证明：（1）对任意n?N,an为正整数；(2)对任意n?N,anan?1证明：（1）由题设得
a1?5,且{an}严格单调递增.将条件式变形得
22an?1?7an?45an?36,两边平方整理得
a27a2n?1?nan?1?an?9?0
①
?a2?7a2nn?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?ab?1.
③
由③式及a0?1,a1?5可知，对任意n?N,an为正整数.
（2）将①两边配方，得(an?1?an)2?9(anan?1?1),?anan?1?1?(an?1an3)2. ④
由③式an?1?an?9an?(an?1?an)≡?(an?an?1)?mod3?
∴an1?ann?1?an≡(?1)?a1?a0?≡0（mod3）∴
an?3为正整数，④式成立.
?anan?1?1是完全平方数.
例8．若
3n?1n(2n?1)可以写成有限小数，那么自然数n的值是多少？
解：由于(n,3n?1)?1
若3n?1与2n?1互素，则分数p?3n?1n(2n?1)是既约分数；
若
3n?1与
2n?1不互素，设它们的公约数为
d，且
d?1，设
3n?1?da,2n?1?db，d(2a?3b)?2(3n?1)?3(2n?1)?5，故3n?1与2n?1的公约数是5，此时分数p的分子、分母只有公约数5。
由于
p可以写成有限小数，故约分之后p的分母除了2,5以外，没还有其它的公约数，因此n(2n?1)?2k?5m。
因为2n?1是奇数，(n,2n?1)?1，故??n?2k2n?1?5，即2k?1?5m?1。
?m由于5m?1?2(mod4)故2k?1?2(mod4)，从而k?0，即m?0,n?1， 故只有n?1,p才是有限小数。
练习
1． 试求方程
??5?6x??8???15x?75的实数解x。（答案：x?7415,5）
2． 若?(n)?16，试出至少5个n的值。（答案：17，32，34，40，48）
则
3． 试求(199810?1999)50被25除所得的余数。（答案：24）
n4． 设整数n使a?1(modm)，这些n中最小的正整数为?，试证：?|n。特别地，若(a,m)?1，则?|?(m)。
是最小的正整数，故r只能为0，即n??q。
证明：设n??q?r,0?r??，则易知ar?(a?)qar?an?1(modm)，但?25． 设a是任意整数，试证下面形状的数都不是完全平方数：（1）5a?2；（2）5a解：（1）5a?2? （2）5a2?6。
2不同余x2(mod5)；
?6?a2?2?2或3(mod5)，但x2?0或1(mod5)。
x6． 求所有满足8
?15y?17z的正整数三元组(x,y,z)。
第五节 初等数论中的几个重要定理
基础知识
定义（欧拉(Euler)函数）一组数x1,x2,?,xs称为是模m的既约剩余系，如果对任意的1?若(a,m)＝1，则有且仅有一个xj是a对模m的剩余，即a数，?(m)称为欧拉（Euler）函数。
这是数论中的非常重要的一个函数，显然?(1)j?s，(xj,m)?1且对于任意的a?Z，
?xj(modm)。并定义?(m)?s?{1,2,?,m}中和m互质的数的个
?1，而对于m?1，?(m)就是1,2，…，m?1中与m互素的数的个数，比如说
p是素数，则有?(p)?p?1。
引理：?(m)?m?P为质数1（1－）；可用容斥定理来证（证明略）。 ?PP|m?(m)定理1：（欧拉（Euler）定理）设(a,m)＝1，则a证明：取模m的一个既约剩余系b1,b2,?,bs,(s互质，且有abi
?1(modm)。
??(m))，考虑ab1,ab2,?,abs，由于a与m互质，故abj(1?j?s)仍与mabj(?1?i?j?s)，于是对每个1?j?s都能找到唯一的一个1??(j)?s，使得abj?b?(j)(modm)，
这种对应关系?是一一的，从而
?(ab)??b?jj?1j?1ss(j)(modm)??bj(modm)，?a(?bj)?(?bj)(modm)。
sj?1j?1j?1sss?(m,?bj)?1，?as?1(modm)，故a?(m)?1(modm)。证毕。
j?1s分析与解答：要证a数：
?(m)?1(modm)，我们得设法找出?(m)个n相乘，由?(m)个数我们想到1,2,?,m中与m互质的?(m)的个
a1,a2,?,a?(m)，由于
(a,m)＝1，从而aa1,aa2,?,aa?(m)也是与（
m互质的?(m)个数，且两两余数不一样，故），而（
a1?a2???a?(m)?aa1,aa2,?,aa?(m)?a?(m)a1?a2???a?(m)modma1?a2???a?(m)m）＝1，故
a?(m)?1(modm)。
