第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-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是整数
用符号p mod m表示p所属的模m的剩余类，这条性质写成数学表达式就是
p mod m= {p+km（k是整数）}
③整数p、q在模m的同一个剩余类中的充要条件是p、q对模m同余。
这条性质用数学符号就可表示为：p mod m= q mod m
p≡q（mod m）
p≡q（mod m）实际上，同余式就是剩余类等式的一个特殊情况，是集合中的一个元素，前面有关同余的一些性质对剩余类仍然成立。
这条性质表明，对于模m的两个剩余类要么相等，要么它们的交集为空集，因此，模m有
且仅有m个剩余类，它们是：
0modm，1 mod m，2 mod m，…（m―1）mod m。
在解决一些有关模m余数的问题时，我们就可以查看m个数：0，1，2，…，m―1，从而得相应的剩余类的情况，使问题变得异常简单，具体例子，请看后面的例题。
④在任意取定的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+k2m，…，xm+k1m也是模m的一组完全剩余系。
（2）一次同余方程
设m | a，则ax≡b（mod m）叫做模m的一次同余方程。
如果x= x0是方程ax ≡b（mod m）的一个解，那么x= km+x0也是这个方程的一个解。这是因为，如果ax0 ≡b（mod m），那么一定有akm+ax0≡b（mod m），即a(km+x0) ≡b（mod m），这说明如果x=x0是方程ax≡b（mod m）的一个解，那么剩余类x0mod m中的任何一个数也是这个方程的解，这些解都看作是相同的，把剩余类x0mod m称为同余方程ax≡b（mod m）的一个解，记作x≡x0（mod m）
因此，我们在解同余方程的时候，只需在任意取定的模m的一组完全剩余系中求解模m的同余方程，就可获得这个方程的全部解。
二、典型例题：
例1．求证：一定存在整数n，使4n2+27n―12能被5整除，并求出这些数。
分析：可以选模5的一个完全剩余系逐个验算，只要数a使4a2+27a―12能被15整除，那么
剩余类a mod 5中的任何一个整数也满足条件。
解：取模5的一个完全剩余系0，1，2，3，4直接计算可知，3和4满足条件，所以使4n2+27―12能被5整除的所有的整数是n≡3（mod 5）和n≡4（mod 5）。
例2 求使2n-1为7的倍数的所有正整数n．
解 因为23≡8≡1(mod 7)，所以对n按模3进行分类讨论．
(1) 若n=3k，则
2n-1＝(23)k-1＝8k-1≡1k-1＝0(mod 7)；
(2) 若n=3k＋1，则
2n-1=2·(23)k-1=2·8k-1
≡2·1k-1＝1(mod 7)；
(3) 若n=3k＋2，则
2n-1=22·(23)k-1=4·8k-1
≡4·1k-1＝3(mod 7)．
所以，当且仅当3｜n时，2n-1为7的倍数．
例3．m、p、n为自然数，求证：3 | np（n2m+2）
分析：对n按模3进行分类讨论
证明：⑴当n≡0（mod 3）时，np≡0（mod 3），∴np（n2m+2）≡0（mod 3）
⑵当n≡1（mod 3）时，np≡1（mod 3），n2m≡12m≡1（mod 3），
∴np（n2m+2）≡1·（1+2）≡3≡0（mod 3）
⑶当n≡2（mod 3）时，np≡2 p（mod 3），n2m≡（n2）m≡4m≡1m≡1（mod 3）
∴np（n2m+2）≡2 p（1+2）≡2 p·0≡0（mod 3）
所以，对一切自然数n，都有3 | n p（n2m+2）
例4.分别求满足下列条件的最小自然数：
（1）用3除余1，用5除余1，用7除余1。
（2）用3除余2，用5除余1，用7除余1。
（3）用3除余1，用5除余2，用7除余2。
（4）用3除余2，用7除余4，用11除余1。
思路分析：
（1）该数减去1以后，是3，5和7的最小公倍数105，所以该数的是105+1=106
（2）该数减去1以后是5和7的公倍数。因此我们可以以5和7的公倍数中去寻找答案。下面列举一些同时被5除余1，被7除余1的数，即
1，36，71，106，141，176，211，246，……从以上数中寻找最小的被3除余2的数。
36≡0（mod3），71≡2（mod3），符合条件的最小的数是71。
（3）我们首先列举出被5除余2，被7除余2的数，2，37，72，107，142，177，212，247，……
从以上数中寻找最小的被3除余1的数。
（1）用3除余1，用5除余1，用7除余1。
（2）用3除余2，用5除余1，用7除余1。
（3）用3除余1，用5除余2，用7除余2。
（4）用3除余2，用7除余4，用11除余1。
思路分析：
（1）该数减去1以后，是3，5和7的最小公倍数105，所以该数的是105+1=106
（2）该数减去1以后是5和7的公倍数。因此我们可以以5和7的公倍数中去寻找答案。下面列举一些同时被5除余1，被7除余1的数，即
1，36，71，106，141，176，211，246，……从以上数中寻找最小的被3除余2的数。
36≡0（mod3），71≡2（mod3），符合条件的最小的数是71。
（3）我们首先列举出被5除余2，被7除余2的数，2，37，72，107，142，177，212，247，……
从以上数中寻找最小的被3除余1的数。
2（mod3），37≡（mod3）、因此符合条件的最小的数是37。
（4）我们从被11除余1的数中寻找答案。
1，12，23，34，45，56，67，78，89，100，133，144，155，166，177，188，199，210，232，243，……
1（mod3）； 1（mod7）， 不符合
12≡0（mod3）， 12≡5（mod7） 不符合
23≡2（mod3）， 23≡2（mod7） 不符合
34≡1（mod3）， 34≡6（mod7） 不符合
45≡0（mod3）， 45≡3（mod7） 不符合
56≡2（mod3）， 56≡0（mod7） 不符合
67≡1（mod3）， 67≡4（mod7） 不符合
78≡0（mod3）， 78≡1（mod7） 不符合
89≡2（mod3）， 89≡5（mod7） 不符合
100≡1（mod3）， 100≡2（mod7） 不符合
122≡2（mod3）， 122≡3（mod7） 不符合
（4）我们从被11除余1的数中寻找答案。
1，12，23，34，45，56，67，78，89，100，133，144，155，166，177，188，199，210，232，243，……
1（mod3）； 1（mod7）， 不符合
12≡0（mod3）， 12≡5（mod7） 不符合
23≡2（mod3）， 23≡2（mod7） 不符合
34≡1（mod3）， 34≡6（mod7） 不符合
45≡0（mod3）， 45≡3（mod7） 不符合
56≡2（mod3）， 56≡0（mod7） 不符合
67≡1（mod3）， 67≡4（mod7） 不符合
78≡0（mod3）， 78≡1（mod7） 不符合
89≡2（mod3）， 89≡5（mod7） 不符合
100≡1（mod3）， 100≡2（mod7） 不符合
122≡2（mod3）， 122≡3（mod7） 不符合
133≡1（mod3）， 133≡0（mod7） 不符合
144≡1（mod3）， 144≡4（mod7） 不符合
155≡2（mod3），155≡1（mod7） 不符合
166≡1（mod3），166≡5（mod7） 不符合
177≡0（mod3），177≡2（mod7） 不符合
188≡2（mod3），188≡6（mod7） 不符合
199≡1（mod3），199≡3（mod7） 不符合
210≡0（mod3），210≡0（mod7） 不符合
221≡2（mod3），221≡4（mod7） 符合
因此符合条件的数是221。
144≡1（mod3）， 144≡4（mod7） 不符合
155≡2（mod3），155≡1（mod7） 不符合
166≡1（mod3），166≡5（mod7） 不符合
177≡0（mod3），177≡2（mod7） 不符合
188≡2（mod3），188≡6（mod7） 不符合
199≡1（mod3），199≡3（mod7） 不符合
210≡0（mod3），210≡0（mod7） 不符合
221≡2（mod3），221≡4（mod7） 符合
因此符合条件的数是221。
例5.现有70个数排成一行，除了两头的两个数以外，每个数的三倍恰好等于它两边两个数的和，这一行最左边的几个数是这样的：0，1，3，8，21，……，问这一行数最右边的一个数被6除的余数是几？
分析：如果将这70个数一一列出，得到第70个数后，再用它去除以6得余数，总是可以的，但计算量太大。
分析：如果将这70个数一一列出，得到第70个数后，再用它去除以6得余数，总是可以的，但计算量太大。
即然这70个数中：中间的一个数的3倍是它两边的数的和，那么它们被6除以后的余数是否有类似的规律呢？
0，1，3，8，21，55，144，……被6除的余数依次是
0，1，3，2，3，1，0，……
结果余数有类似的规律，继续观察，可以得到：
0，1，3，2，3，1，0，5，3，4，3，5，0，1，3，2，3，……
可以看出余数前12个数一段，将重复出现。
70÷2=5……10，第六段的第十个数为4，这便是原来数中第70个数被6除的余数。
0，1，3，8，21，55，144，……被6除的余数依次是
0，1，3，2，3，1，0，……
结果余数有类似的规律，继续观察，可以得到：
0，1，3，2，3，1，0，5，3，4，3，5，0，1，3，2，3，……
可以看出余数前12个数一段，将重复出现。
70÷2=5……10，第六段的第十个数为4，这便是原来数中第70个数被6除的余数。
例6．解下列同余方程
⑴3x≡2（mod 6） ⑵4x≡6（mod 10）
解：⑴当x≡0（mod 6）时，3x≡0（mod 6）
当x≡1（mod 6）时，3x≡3（mod 6）
当x≡2（mod 6）时，3x≡6≡0（mod 6）
当x≡3（mod 6）时，3x≡9≡3（mod 6）
当x≡4（mod 6）时，3x≡12≡0（mod 6）
当x≡5（mod 6）时，3x≡15≡3（mod 6）
所以方程3x≡2（mod 6）无解。
⑵与⑴小题类似，取模10的最小完全剩余系0，1，2，3，…，9直接计算可知，x=4和x=9是方程的解，所以这个同余方程的解为x≡4（mod 10）或x≡9（mod 10）
说明：①解模m的一次同余方程，可以取模m的一个完全剩余系直接计算，这个方法也适用于其它的同余方程。
②模m的一次同余方程ax≡b（mod m）（m 
a）有解的充要条件是（a，m）| b。
a）有解的充要条件是（a，m）| b。例7. 同余方程2x≡6（mod 8）的解和方程x≡3（mod 4）的解是否相同，说明理由。
解：设x=x0是方程2x≡6（mod 8）的一个解，那么2x0≡6（mod 8）
∴2x0=8 k+6，x0= 4k+3，∴x0≡3（mod 4）
即方程2x≡6（mod 8）的解必是方程x≡3（mod 4）的解
反之，若x=x0是方程x≡3（mod 4）的一个解，那么x0≡3（mod 4）
∴x0= 4m+3，∴2x0=8m+6，故2x0≡6（mod 8）
即方程x≡3（mod 4）的解必是方程2x≡6（mod 8）的解
所以，方程2x≡6（mod 8）和x≡3（mod 4）的解相同
说明：若正整数d | （a，b，m），则方程ax≡b（mod m）的解与方程
的解相同，利用这条性质可以将较大模数的同余方程化为较小模数的同余方程。
的解相同，利用这条性质可以将较大模数的同余方程化为较小模数的同余方程。例8．解同余方程38x≡－19（mod 95）
分析：此题中的模95的剩余数太多，如果选定一个完全剩余系进行直接计算，运算量相当大，因此我们可以运用上题的方法，将模化小一点。
解：∵（38，19，95）=19，∴38x≡－19（mod 95）的解与2x≡－1（mod 5）的解完全相同，只需求解方程2x≡－1（mod 5）即可。
∵2x≡－1（mod 5），∴2x≡4（mod 5）
∵x≡2（mod 5），∴原方程的解为x≡2+5u（u=0，1，2，3，…，18）（mod 95）
例9 证明：在十进制表示下，任意39个连续正整数中，必有一个数的各位数字之和是11的倍数。
例10.设n位为正奇数，证明：数2-1，22-1，23-1，…，2n-1-1中必有一个数是n的倍数。
例11.一次圆桌会议共有2012个人参加，中场休息后，他们依不同的次序重新围着圆桌坐下，证明：至少有两个人，他们之间的人数在休息前后是相等的。
三、模拟训练
1 证明方程
x4+y4+2=5z
没有整数解．
证 对于任一整数x，以5为模，有
x≡0，±1，±2(mod 5)，
x2≡0，1，4(mod 5)，
x4≡0，1，1(mod 5)，
即对任一整数x，
x4≡0，1(mod 5)．
同样，对于任一整数y
👁️ 阅读量：0
© 版权声明：本文《初中数学竞赛讲座——数论部分8(同余系的应用)》内容均为本站精心整理或网友自愿分享，如需转载请注明原文出处：https://www.zastudy.cn/jiangzuo/1686216060a207800.html。