资源描述：
《初中数学竞赛讲座——数论部分8(同余系的应用).doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第8讲剩余系及其一次同余方程一、基础知识：（1）剩余系对于任意正整数n而言，一个整数除以m所得的余数只能是0,1,2,…,n-1中的某一个。依次可将整数分成n个类（例如n＝2时，就是奇数或偶数），从每一类中各取一个数所组成的集合就称为模的一个完全剩余系，简称为模的完系。定义1：如果一个剩余系中包含了这个正整数所有可能的余数（一般地，对于任意正整数n，有n个余数：0,1,2,...,n-1），那么就被称为是模n的一个完全剩余系。定义2：剩余系：设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-
2、1]，这m个数{0,1,2,…m-1}称为一个完全剩余系，每个数称为相应类的代表元。例如：当m=10则,{0,1,2,3,4,5,6,7,8,9} 最小非负完全{-5,-4,-3,-2,-1,0,1,2,3,4} 绝对值最小{-4,-3,-2,-1,0,1,2,3,4,5} 绝对值最小（一）根据剩余类的概念，很容易得到以下几条有关剩余类的性质：①每一个整数一定包含在而且仅包含在模m的一个剩余类中②整数p所属的模m的剩余类中的每一个数都可以写成km+p的形式，这里k是整数用符号pmodm表示p所属的模m的剩余类，这条性质写成数
3、学表达式就是pmodm={p+km（k是整数）}③整数p、q在模m的同一个剩余类中的充要条件是p、q对模m同余。这条性质用数学符号就可表示为：pmodm=qmodmp≡q（modm）实际上，同余式就是剩余类等式的一个特殊情况，是集合中的一个元素，前面有关同余的一些性质对剩余类仍然成立。这条性质表明，对于模m的两个剩余类要么相等，要么它们的交集为空集，因此，模m有且仅有m个剩余类，它们是：0modm，1modm，2modm，…（m―1）modm。在解决一些有关模m余数的问题时，我们就可以查看m个数：0，1，2，…，m―1，从而
4、得相应的剩余类的情况，使问题变得异常简单，具体例子，请看后面的例题。④在任意取定的m+1个整数中，必有两个整数对模m同余。（二）根据同余式的性质，我们很容易得到剩余系的其它一些性质：⑤m个整数x1，x2，…，xm是模m的一组完全剩余系的充要条件是x1，x2，…，xm中的任意两个数对模m都不同余。⑥如果x1，x2，…，xm是模m的一组完全剩余系，那么对任意的整数c，x1+c，x2+c，…，xm+c也是模m的一组完全剩余系。⑦设k1，k2，…，km是m个整数，如果x1，x2，…，xm是模m的一组完全剩余系，那么x1+k1m，x2
5、+k2m，…，xm+k1m也是模m的一组完全剩余系。（2）一次同余方程设m
6、a，则ax≡b（modm）叫做模m的一次同余方程。Word资料如果x=x0是方程ax≡b（modm）的一个解，那么x=km+x0也是这个方程的一个解。这是因为，如果ax0≡b（modm），那么一定有akm+ax0≡b（modm），即a(km+x0)≡b（modm），这说明如果x=x0是方程ax≡b（modm）的一个解，那么剩余类x0modm中的任何一个数也是这个方程的解，这些解都看作是相同的，把剩余类x0modm称为同余方程ax≡b（modm）的一个
7、解，记作x≡x0（modm）因此，我们在解同余方程的时候，只需在任意取定的模m的一组完全剩余系中求解模m的同余方程，就可获得这个方程的全部解。二、典型例题：例1．求证：一定存在整数n，使4n2+27n―12能被5整除，并求出这些数。分析：可以选模5的一个完全剩余系逐个验算，只要数a使4a2+27a―12能被15整除，那么剩余类amod5中的任何一个整数也满足条件。解：取模5的一个完全剩余系0，1，2，3，4直接计算可知，3和4满足条件，所以使4n2+27―12能被5整除的所有的整数是n≡3（mod5）和n≡4（mod5）。例
8、2求使2n-1为7的倍数的所有正整数n． 解因为23≡8≡1(mod7)，所以对n按模3进行分类讨论． (1)若n=3k，则2n-1＝(23)k-1＝8k-1≡1k-1＝0(mod7)； (2)若n=3k＋1，则2n-1=2·(23)k-1=2·8k-1 ≡2·1k-1＝1(mod7)； (3)若n=3k＋2，则2n-1=22·(23)k-1=4·8k-1 ≡4·1k-1＝3(mod7)． 所以，当且仅当3｜n时，2n-1为7的倍数．例3．m、p、n为自然数，求证：3
9、np（n2m+2）分析：对n按模3进行分
10、类讨论证明：⑴当n≡0（mod3）时，np≡0（mod3），∴np（n2m+2）≡0（mod3）⑵当n≡1（mod3）时，np≡1（mod3），n2m≡12m≡1（mod3），∴np（n2m+2）≡1·（1+2）≡3≡0（mod3）⑶当n≡2（mod3）时，np≡2p（mod3），n2m≡
