初中数学竞赛讲座 - 数论部分8（同余系的应用）

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

第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）

实际上，同余式就是剩余类等式的一个特殊情况，是集合中的一个元素，前面有关同余的一些性质对剩余类仍然成立。

这条性质表明，对于模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也是这个方程的一个解。

第 1 页 共 9 页

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

这是因为，如果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）。

n

例2 求使2-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的数，即

第 2 页 共 9 页

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

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） 不符合 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。

例5.现有70个数排成一行，除了两头的两个数以外，每个数的三倍恰好等于它两边两个

数的和，这一行最左边的几个数是这样的：0，1，3，8，21，??，问这一行数最右边的一个数被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除的余数。

第 3 页 共 9 页

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

例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。 例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）的解与方程

abmx?(mod)ddd的解相同，利用这条性质可以将较大模数的同余方程化为较小模数的同余方程。

例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的倍数。

第 4 页 共 9 页

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

例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

y4≡0，1(mod 5)，

所以 x4+y4+2≡2，3，4(mod 5)， 从而所给方程无整数解．

第 5 页 共 9 页

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

说明 同余是处理不定方程的基本方法，但这种方法也非常灵活，关键在于确定所取的模(本例我们取模5)，这往往应根据问题的特点来确定．

2．解同余方程987x≡610（mod 1597）

解：∵987x≡610（mod 1597），∴987x－1597x≡610（mod 1597） －610x≡610（mod 1597），x≡－1（mod 1597） 3．请看一首欢庆国庆的诗：“十里长街闹盈盈，庆祝成就万象新，国庆礼花破长空，新

桥红灯胜繁星，七七数时余两个，五个一数恰为零，九数之时剩四盏，红灯几盏放光明。”

解：设有x盏红灯，那么

??x≡2（mod 7） ①?x≡0（mod 5） ② ?x≡4（mod 9） ③?

由①得x=7m+2，m=0，1，2，3，?， 代入②得，7m+2≡0（mod 5），7m≡―2≡―2+5×6≡28（mod 5） ∴m≡4（mod 5），∴m≡5n+4，∴x=7（5n+4）+2=35n+30 代入③得，35n+30≡4（mod 9），

35n≡―26≡―26+4×9≡10（mod 9） ∴7n≡2（mod 9），7n≡2+6×9≡56（mod 9），n≡8（mod 9） ∴n=9k+8，k=0，1，2，3，?，

所以x=35（9k+8）+30=315k+310，xmin=310， 答：有310盏红灯。 【延伸阅读】

我国南北朝时期有一部著名的算术著作《孙子算经》，其中有这样一个“物不知数”问题：“今有物不知其数，三三数之剩2；五五数之剩3；七七数之剩2，问物几何？”用现在化较通俗的数学语言可以这样叙述：“求一个数，使它被3除余2；被5除余3；被7除余2。”

??x≡2（mod 3） ①

解：设所求数为x，则?x≡3（mod 5） ②

??x≡2（mod 7） ③

由①得x=3k+2，k=0，1，2，3?

代入②得，3k+2≡3（mod 5） ∴3k≡1≡1+5≡6（mod 5），∴k≡2（mod 5），即k= 5n+2，n=0，1，2，?， ∴x=3（5n+2）+2=15n+8，n=0，1，2，3，?， 代入③得：15n+8≡2（mod 7），15n≡―6≡―6+21≡15（mod 7） ∴n≡1（mod 7），故n=7t+1，t=0，1，2，?

所以，x=15（7t+1）+8=105t+23，t=0，1，2，3，?，所求数的最小值是23。

《孙子算经》巧妙地解决了“物不知数”问题，但没有上升到一套完整的计算程序

第 6 页 共 9 页

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

和理论高度，没有解决一般的一次同余方程的求解问题，南宋时期的数学家秦九韶在他的《数学九章》中提出了“大衍求一术”的数学方法，系统地论述了一次同余方程组解法的基本原理和一般程序。“求一”就是求一个数的多少倍除以另一个数，所得的余数是一，为了深刻地理解这一方法，我们再回头研究“物不知数”问题中的几个关键数字71，21、15。

70=2×5×7≡1（mod 3） 21=3×7≡1（mod 5） 15=3×5≡1（mod 7）

其中，70是5和7的倍数，但被3除余1，21是3和7的倍数，但被5除1；15是3和5的倍数，但被7除余1，任何一个一次同余方程组，只要类似地求出相应的关键数字，就可以得到这个一次同余方程组的解，秦九韶的“大衍求一术”的方法流传到西方，被称为“中国剩余定理”。

所以，我得到一般一次同余方程组的解法是：设p，q，r是两面互质的正整数，同余方程组

??x≡a（mod p）

?x≡b（mod q）的解是x≡Aa+Bb+Cc（mod pqr） ??x≡c（mod r）

其中

A≡1（mod p），A≡0（mod q），A≡0（mod r）

B≡1（mod q），B≡0（mod p），B≡0（mod r） C≡1（mod r），C≡0（mod p），C≡0（modq） 下面我们介绍中国剩余定理：

【中国剩余定理】设m1，m2，?，m k是k个两两互质的正整数，对任意整数a1，a2，?，a k，则同余方程组。

???

x≡a1（mod m1）x≡a2（mod m2）

有且只有一个解

?

x≡a k（mod m k）

?1?11x ≡M1M1a1+M2M2a2+?+M kM?ka k（mod m）其中m=m1m2?m k，

1m = mjMj（1≤j≤k）以及M jM?≡1（mod mj）1≤j≤k j这个定理本身比较复杂，证明也比较繁，关于证明过程，这里不作介绍，有兴趣的同学请自行阅读有关初等数论的著作，只对定理本身作一些阐述，以帮助大家理解，我们用中国剩余定理再解“物不知数”问题。

M1=5×7=35，M2=3×7=21，M3=3×5=15，35×2=70≡1（mod 3） 21≡1（mod 5），15≡1（mod 7）

∴M1M1=70，M2M2=21，M3M3=15

第 7 页 共 9 页

?1?1?1初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

∴x≡70×2+21×3+15×2（mod 105）≡233≡23（mod 105） 所以x的最小值是23。

下面举例说明中国剩余定理的运用。 例1．解同余方程组

??x≡1（mod 5）?x≡－1（mod 7） ??x≡－2（mod 11）

解：m1=5，m2=7，m3=11

∴M1=7×11=77，M2=5×11=55，M3=5×7=35

?1?1∵M1≡7×11≡2×1≡2（mod 5），由1≡M1M1≡2M1（mod 5）得，可取M1=3

—

?11∵M2≡5×11≡5×4≡20≡6≡－1（mod 7），由1≡M1M1≡－M?2（mod 7）得， 1可取M?2=6

?1?1?1∵M3≡35≡2（mod 11），由1≡M3M3≡2M3（mod 11）得，可取M3=6

由中国剩余定理可知，原同余方程组的解为

x≡77×3×1+55×6×（－1）+35×6×（－2）×7×11） ≡－519（mod 385）≡251（mod 385） ≡1（mod 3）?x－x≡1（mod 5）

例2．解同余方程组?

－2x≡3（mod 7）?－3x≡6（mod 11）

分析：这不是中国剩余定理的形，我们可以先将方程中的“系数”化为1，再运用中国剩余定理求解。

x≡1（mod 3）x≡－1（mod 5）

解：原方程组与同余方程组的解相同。

x≡2（mod 7）x≡-2（mod 11）

???

∴m1=3，m2=5，m3=7，m 4=11

∴M1=5×7×11，M2=3×7×11，M3=3×5×11，M 4=3×5×7， 因M1≡2×1×2≡4≡1（mod 3），所以可取M1=1 因M2≡3×2×1≡6≡1（mod 5）所以可取M2=1

?1?1?1因M3≡3×5×4≡60≡4（mod 7），由1≡M3M3≡4 M3（mod 7）得，可取M3=2

?1?1第 8 页 共 9 页

初中数学兴趣班系列讲座——数论部分 唐一良数学工作室

1?11因M4≡3×5×7≡105≡6（mod 11），由1≡M4M?得，可取M?4≡6 M4（mod 11）4=2

根据中国剩余定理知，原方程组的得为

x≡（5×7×11）×1×1+（3×7×11）×1×（－1） +（3×5×11）×2×2+（3×5×7）×2×（－2）（mod 3×5×7×11） ≡385－231+660－420（mod 1155 ）≡394（mod 1155 ）

至此，我们完整地介绍了模两两互质的一次同余方程组的解法，归纳起来主要有两种解法。一种解法是根据同余的定义，逐步代入的方法。另一种方法根据定理的求解公式直接求解。这里的中国剩余定理与孙子解法的实质是相同的，因此这一定理又叫“孙子定理”或“孙子剩余定理”。根据同余的定义，逐个选代解方程的过程中，关键是得到到形如“x≡b（mod m）”的同余方程，运用定理解同余方程，关键在“求一”。

第 9 页 共 9 页

本文来源：https://www.bwwdw.com/article/s8uh.html