第三章
第十一节 同余问题
093数教 黄欢 01号
在整数除法运算中，被除数与除数可能是整除关系，也可能不是整除关系。而许多问题，只
需要知道余数。由此形成了专门研究余数的问题，即同余问题。
一、带余除法的定义
如果a，b是两个整数，b>0，那么一定有而且只有两个整数q，r使
a=bq+r，（0≤r
我们称r为a除以b的余数，q为a除以b的不完全商。
整数集合是可按余数分类。一个整数被正整数b除时，余数只有0，1，2，…，
b-1这b种情况。我们把被b除同时都余r (0≤r＜b)的一类数，叫做b的剩余
类。因此，数b的剩余类共有b个。这样整数就被分成b类。
比如，一个整数被2除时的余数只能是0和1，所以整数可分为两类，即余
数为0的偶数，记为2k，余数为1的奇数，记为2k+1，其中k为任意整数。
一个整数被3除时的余数只能是0和1，2，所以整数可分为三类，即被3整
除的一类，记为3k，被3除余1的一类，记为3k+1，被3除余2的一类，记为
3k+2，其中k取任意整数。
二、同余的概念
两个整数a与b除以整数m（m>0），如果余数相同，则称a与b关于模m同余。
并用下面的同余式表示
a≡b(mod m).
a≡b(mod m) a=b+km,(k∈N) m|(a-b).
同余的概念和记号都是德国数学家高斯在他的名著《算术研究》（1801年）中
引进的，是研究数论的重要工具。
三、同余的性质
1.（反身性）a≡a(mod m)；
2.(对称性) 如果a≡b(mod m)；那么b≡a(mod m)；
3.（传递性）如果a≡b(mod m),b≡c(mod m),那么a≡c(mod m)；
4.如果a≡b(mod m),c≡d(mod m),那么a±b≡c±d(mod m)；
5.a+b≡c(mod m)当且仅当a≡c-b(mod m)；
6.如果a≡b(mod m),c≡d(mod m),那么ac≡bd(mod m),an≡bn(mod m),(n为
正整数)，ak≡bk(mod m) (k为正整数)。
例1 从自然数1，2，3，…，1000中，最多可取出多少个数使得所取出的数
中任意三个数之和能被18整除？
【解】设a,b,c,d是所取出的数中的任意4个数，依题意任意三个数之和能
被18整除，则a+b+c,a+b+d也能被18整除。
设a+b+c=18q1,a+b+d=18q（相减得c-d=18(q1-q2),所以18|（c-d）,2q1,q2∈N）
所以c≡d(mod m).
由于c,d的任意性，说明所取的每一个数除以18所得的余数均想同。设
a=18a1+r,b=18b1+r,c=18c1+r,
其中a1,b1,c1∈N,0≤r＜18,
a+b+c=18(a1+b1+c1)+3r.
因为18|（a+b+c）,所以18|(3r),即6|r,所以r=0,6,12.
因此，需要从1，2，3，…，1000这1000个数中把被18整除的数和被
18除余6，余12的数全部取出来。因为
1000÷18=55……10
所以，最多取出55+1=56个符合要求的数，它们分别是6，24，42，…，996.
如果取被18整除的数或被18除余12的数，则只能取出55个.
例2 证明任意平方数除以8的余数为0，1，或4.（这是平方数的重要特征）
【证明】对整数分类讨论：
（1）若n=2k+1,k∈N,则n2=(2k+1)2=4k2+4k(k+1)+1.因为k(k+1)为偶数，所以
8|4k（k+1）,所以n2≡1(mod 8).
22 (2)若n=2k,k∈N,则n=4k.
①当k=2t,t∈N时，n2=4k2=4(2t)2=16t2≡0(mod 8)
②当k=2t+1,t∈N时，n=4k=4(2t+1)=4(4t+4t+1) =16(t+t)+4≡4(mod 8).所以
n2≡0(mod 8)，或n2≡1(mod 8)，或n2≡4(mod 8)。 22222
例3（1）求32003除以13的余数；（2）今天是星期四，再过4737天是星期几？（3）
358124求47+52×279的末尾数字。
【解】（1）∵ 33=27≡1（mod 13）,
∴32003=33×667+2=(33)667×32≡1667×32≡9(mod 13),
所以32003除以13余9.
【说明】求余数是同余的基本问题，在这种问题中，先求出与±1同余的数是一
种基本的解题技巧。
(2)【分析】因为再过7天又是星期四，所以问题的关键是求出473723除以7的余
数。
∵ 47≡5（mod 7）,
∴ 472≡52=25≡4(mod 7) ,
∴ 474≡42=16≡2(mod 7),
∴ 476≡4×2=8≡1(mod 7).
23+23下面考虑把37写成6k+rr的形式，k,r∈Z且0≤r＜6,即求37除以6的余数。
∴ 37≡1（mod 6）,
2323∴ 37≡ 1=1(mod 6)
∴ 3723=6k+1,(k∈Z+),
∴
∴
4737473723=476k+1=（476）k×47≡1k×47≡5(mod 7), 除以7余5. 23
所以，今天是星期四，再过473723天就是星期二。
(3)【分析】求末位数字就是求这个数被10除的余数。可从下表观察出如下结论：
4k+114k+22 a≡a(mod 10),a≡a(mod 10),
a4k+3≡a3(mod 10),a4k+4≡a4(mod 10).
其中k为自然数。
以81×27924的末位数字是5.
例4有兵一队，若列成五行，剩余1人；列成六行，剩余5人；列成七行，剩余
4人；列成11行，剩余10人；那么至少有兵多少人？
【解】依题意，设至少有兵x人，则得下列同余式组
≡1(mod 5), …①
≡5(mod 6), …②
≡4(mod 7), …③
≡10(mod 11). …④
由①得：
x=5k1+1,k1为自然数。 …⑤
在⑤式中选取k1,找出满足②式的最小的x,实验可知k1=2,x最小为11，所以
≡11(mod 5),
又[5,6]=30
x≡11(mod 6).
所以x≡11(mod 30),即
x=11+30k2,k2为自然数。 …⑥
在⑥中选取k2,找出满足③式的最小的x,实验可知k2=0,x最小为11，所以
≡11(mod 30),
≡11(mod 7)
又[30,7]=210，所以x≡11(mod 210),即
x=11+210k3,k3为自然数。 …⑦
在⑦中选取k3,找出满足④式的最小的x,实验可知k3=10,x最小为2111，所以
≡2111(mod 210), ≡2111(mod 11) 又[210,11]=2310，所以x≡2111(mod 2310),即为同余式组的解，2111为最小的正整数。所以至少有兵2111人。
以上是用实验法找出符合条件的数。
我国古代数学家解决这类问题的方法是根据中国剩余定理，对此有兴趣的读者可以查阅处等数论教材。
例5.44444444的数字之和为A，A的数字之和为B，B的数字之和为C，求C。
【解】∵一个数字与其数字之和关于模
444444443×1481+131481 ∴ C≡B≡A＝4444≡7＝7=（7）×7
=(343)1481×7≡11481×7≡7(mod 9)
∴ C=7.
例6 111…1被1989除余1，求最小的正整数n.
个1
【解】 1989=9×13×17，而9，13，17两两互质，所以111…1被1989除余1， ＋1个1
n 即111…1分别被9，13，17除均余1.又10≡(mod 9),
1个1
2310≡10(mod 17), 10≡9(mod 17), 10≡90≡12(mod 17),
104≡140≡4(mod 17), 105≡40≡6(mod 17), 106≡60≡9(mod 17), 78910≡9≡5(mod 17), 10≡16(mod 17), 10≡24≡7 (mod 17),
1010≡2(mod 17), 1011≡20≡3mod 17), 1012≡30≡13(mod 17), 1013≡45≡11(mod 17), 1014≡25≡8(mod 17), 1015≡12(mod 17), 1016≡52≡1(mod 17).
以后开始循环。
111…1=1+10+102 +…+10n ≡1＋1+1+…+1=n+1(mod 9),
1个1个1
所以，当n≡0(mod 9),即9|n时，111…1≡1(mod 9).
个1
2n 111…1=1+10+10 +…+10 ≡1＋10+9+12+3+4+1+10+9+12+3+4+1+…
1个个
=1+39+39+…（mod 13）,所以，6|n时，111…1≡1(mod 13),
1个1
2n 111…1=1+10+10 +…+10
1个1
=1＋10＋15＋14＋4＋6＋9＋5＋16＋7＋2＋3＋13＋11＋8＋12＋1＋…
16个
=1＋136＋…（mod 17）,所以，16|n时，111…1≡1(mod 17).
1个1
为使n最小，n应为9，6，16的最小公倍数，即n=144.
例7 下图3-103的七张卡片中有3张上面的数是未知整数。这3个未知整数都
是3的倍数，并且这3个数的和是180.有三个学生，每人取走2张卡片，各自的两张卡片上的数的和都彼此相同，请问剩下的1张卡片上写的数是几？
图3-103
【解】设三个未知整数分别为x1,x2,x3,那么
34≡46≡61≡79≡1（mod 3）, x1≡x2≡x3≡0(mod 3).
七张卡片上7个数的和为：
34+46＋61＋79＋180=400≡1（mod 3）
由于三个学生每人取走的两张卡片上数的和都是彼此相等，所以，取走的这6张卡片上的数的总和被3整除。因此，剩下的1张卡片上的数是被3除余1.即剩下的卡片上的数是34，46，或79.
若剩下的是标有34的卡片，则每人手中两张卡片数的和为：
（400-34）÷3=122≡2（mod 3）.
这就需要每人取走的两张卡片上的数都应被3除余1，但实际上我们只有四张这样的卡片。因此不可能剩下标有34的卡片。同理，也不可能剩下标有61或79的卡片，经捡验，剩下的卡片上写的数应为46.
例8 在黑板上写数1，2，3，…，1986，1989。然后从所写的数中擦去某些数，同时，写上它们的和除以7的余数，这叫一次操作。若干次操作之后，在黑板上剩下的两个数，其中之一是987，那么剩下的另一个数是几？
【解】设A被7除的余数为rA ，0 ≤rA ＜7.即
A ≡rA (mod 7) .
其中A=1＋2＋…＋1986＋1987=（1+1987）×1987=1987×7×142≡（mod 7）,21
即rA=0.
设第一次擦去的数之和为B，B被7除余数为rB，0≤rB ＜7，即
B≡rB (mod 7) .
①-②得A-B≡rA- rB(mod 7)，即
A-B+ rB ≡rA (mod 7) 。
③式说明操作一次，黑板上数之和仍为被7除余rA.若干次操作之后，设剩下的另一个数是x，则987+x≡rA (mod 7)，即x≡0 (mod 7).
因为987不是除以7的余数，按操作可知，数x就是除以7的余数， 即0≤x＜7，所以x=0.即剩下的另一个数为0.
1.小马虎在座一道有余数的除法时，降被除数237错写成273，计算出结果商比正确答案多3，而余数恰好相同。请问这道题的除数是几？
2.甲、乙、丙三数分别为603，939，393，某数A除甲数所得余数是A除乙数所得余数的两倍，A除乙数所得余数是A除丙数所得余数的两倍，则A等于几？
3.31001×71002×131003×171004的个位数字是几？
4.1986年春节（2月9日）是星期日，问2005年的六一儿童节是星期几？ 5. 1010＋1010＋1010＋…＋1010除以7的余数。
12310
6.证明：19911991＋19921992不是平方数。
7.把由1开始的正整数依次写下去，一直写到第189位上，[**************]13…，那么，这个数用9除的余数是多少？
20048.2004写成一个多位数后，它的数字之和为A，A的数字之和为B，B的数字之和为C，求C。
9.一支总人数是5的倍数，且不少于1000热播的游行队伍，若按每横排4热播编队，最后是3人；若每横排3人编队，最后是2人；若每横排2人编队，最后是1人。求这支队伍至少有多少人？
10.n是使111…1被1989除余1的最小的正整数n.
1
（1）p=11…1 99…9 88…8 99…9被1989除余数是几？
n个1 n个9 n个8 n个9
（2） q=111…1被1989除余数是几？
11.在一张纸上连续写下：[**************]9…321.把第一个数字1乘2加上第2个数字9，然后再乘2加上第三个数字9，再乘2加上第四个数字2，……，一直加到最后一个数字1，得到一个新数，这叫一个操作。若干次操作之后，得到一个一位数，请问这个一位数是几？
第三章
第十一节 同余问题
093数教 黄欢 01号
在整数除法运算中，被除数与除数可能是整除关系，也可能不是整除关系。而许多问题，只
需要知道余数。由此形成了专门研究余数的问题，即同余问题。
一、带余除法的定义
如果a，b是两个整数，b>0，那么一定有而且只有两个整数q，r使
a=bq+r，（0≤r
我们称r为a除以b的余数，q为a除以b的不完全商。
整数集合是可按余数分类。一个整数被正整数b除时，余数只有0，1，2，…，
b-1这b种情况。我们把被b除同时都余r (0≤r＜b)的一类数，叫做b的剩余
类。因此，数b的剩余类共有b个。这样整数就被分成b类。
比如，一个整数被2除时的余数只能是0和1，所以整数可分为两类，即余
数为0的偶数，记为2k，余数为1的奇数，记为2k+1，其中k为任意整数。
一个整数被3除时的余数只能是0和1，2，所以整数可分为三类，即被3整
除的一类，记为3k，被3除余1的一类，记为3k+1，被3除余2的一类，记为
3k+2，其中k取任意整数。
二、同余的概念
两个整数a与b除以整数m（m>0），如果余数相同，则称a与b关于模m同余。
并用下面的同余式表示
a≡b(mod m).
a≡b(mod m) a=b+km,(k∈N) m|(a-b).
同余的概念和记号都是德国数学家高斯在他的名著《算术研究》（1801年）中
引进的，是研究数论的重要工具。
三、同余的性质
1.（反身性）a≡a(mod m)；
2.(对称性) 如果a≡b(mod m)；那么b≡a(mod m)；
3.（传递性）如果a≡b(mod m),b≡c(mod m),那么a≡c(mod m)；
4.如果a≡b(mod m),c≡d(mod m),那么a±b≡c±d(mod m)；
5.a+b≡c(mod m)当且仅当a≡c-b(mod m)；
6.如果a≡b(mod m),c≡d(mod m),那么ac≡bd(mod m),an≡bn(mod m),(n为
正整数)，ak≡bk(mod m) (k为正整数)。
例1 从自然数1，2，3，…，1000中，最多可取出多少个数使得所取出的数
中任意三个数之和能被18整除？
【解】设a,b,c,d是所取出的数中的任意4个数，依题意任意三个数之和能
被18整除，则a+b+c,a+b+d也能被18整除。
设a+b+c=18q1,a+b+d=18q（相减得c-d=18(q1-q2),所以18|（c-d）,2q1,q2∈N）
所以c≡d(mod m).
由于c,d的任意性，说明所取的每一个数除以18所得的余数均想同。设
a=18a1+r,b=18b1+r,c=18c1+r,
其中a1,b1,c1∈N,0≤r＜18,
a+b+c=18(a1+b1+c1)+3r.
因为18|（a+b+c）,所以18|(3r),即6|r,所以r=0,6,12.
因此，需要从1，2，3，…，1000这1000个数中把被18整除的数和被
18除余6，余12的数全部取出来。因为
1000÷18=55……10
所以，最多取出55+1=56个符合要求的数，它们分别是6，24，42，…，996.
如果取被18整除的数或被18除余12的数，则只能取出55个.
例2 证明任意平方数除以8的余数为0，1，或4.（这是平方数的重要特征）
【证明】对整数分类讨论：
（1）若n=2k+1,k∈N,则n2=(2k+1)2=4k2+4k(k+1)+1.因为k(k+1)为偶数，所以
8|4k（k+1）,所以n2≡1(mod 8).
22 (2)若n=2k,k∈N,则n=4k.
①当k=2t,t∈N时，n2=4k2=4(2t)2=16t2≡0(mod 8)
②当k=2t+1,t∈N时，n=4k=4(2t+1)=4(4t+4t+1) =16(t+t)+4≡4(mod 8).所以
n2≡0(mod 8)，或n2≡1(mod 8)，或n2≡4(mod 8)。 22222
例3（1）求32003除以13的余数；（2）今天是星期四，再过4737天是星期几？（3）
358124求47+52×279的末尾数字。
【解】（1）∵ 33=27≡1（mod 13）,
∴32003=33×667+2=(33)667×32≡1667×32≡9(mod 13),
所以32003除以13余9.
【说明】求余数是同余的基本问题，在这种问题中，先求出与±1同余的数是一
种基本的解题技巧。
(2)【分析】因为再过7天又是星期四，所以问题的关键是求出473723除以7的余
数。
∵ 47≡5（mod 7）,
∴ 472≡52=25≡4(mod 7) ,
∴ 474≡42=16≡2(mod 7),
∴ 476≡4×2=8≡1(mod 7).
23+23下面考虑把37写成6k+rr的形式，k,r∈Z且0≤r＜6,即求37除以6的余数。
∴ 37≡1（mod 6）,
2323∴ 37≡ 1=1(mod 6)
∴ 3723=6k+1,(k∈Z+),
∴
∴
4737473723=476k+1=（476）k×47≡1k×47≡5(mod 7), 除以7余5. 23
所以，今天是星期四，再过473723天就是星期二。
(3)【分析】求末位数字就是求这个数被10除的余数。可从下表观察出如下结论：
4k+114k+22 a≡a(mod 10),a≡a(mod 10),
a4k+3≡a3(mod 10),a4k+4≡a4(mod 10).
其中k为自然数。
以81×27924的末位数字是5.
例4有兵一队，若列成五行，剩余1人；列成六行，剩余5人；列成七行，剩余
4人；列成11行，剩余10人；那么至少有兵多少人？
【解】依题意，设至少有兵x人，则得下列同余式组
≡1(mod 5), …①
≡5(mod 6), …②
≡4(mod 7), …③
≡10(mod 11). …④
由①得：
x=5k1+1,k1为自然数。 …⑤
在⑤式中选取k1,找出满足②式的最小的x,实验可知k1=2,x最小为11，所以
≡11(mod 5),
又[5,6]=30
x≡11(mod 6).
所以x≡11(mod 30),即
x=11+30k2,k2为自然数。 …⑥
在⑥中选取k2,找出满足③式的最小的x,实验可知k2=0,x最小为11，所以
≡11(mod 30),
≡11(mod 7)
又[30,7]=210，所以x≡11(mod 210),即
x=11+210k3,k3为自然数。 …⑦
在⑦中选取k3,找出满足④式的最小的x,实验可知k3=10,x最小为2111，所以
≡2111(mod 210), ≡2111(mod 11) 又[210,11]=2310，所以x≡2111(mod 2310),即为同余式组的解，2111为最小的正整数。所以至少有兵2111人。
以上是用实验法找出符合条件的数。
我国古代数学家解决这类问题的方法是根据中国剩余定理，对此有兴趣的读者可以查阅处等数论教材。
例5.44444444的数字之和为A，A的数字之和为B，B的数字之和为C，求C。
【解】∵一个数字与其数字之和关于模
444444443×1481+131481 ∴ C≡B≡A＝4444≡7＝7=（7）×7
=(343)1481×7≡11481×7≡7(mod 9)
∴ C=7.
例6 111…1被1989除余1，求最小的正整数n.
个1
【解】 1989=9×13×17，而9，13，17两两互质，所以111…1被1989除余1， ＋1个1
n 即111…1分别被9，13，17除均余1.又10≡(mod 9),
1个1
2310≡10(mod 17), 10≡9(mod 17), 10≡90≡12(mod 17),
104≡140≡4(mod 17), 105≡40≡6(mod 17), 106≡60≡9(mod 17), 78910≡9≡5(mod 17), 10≡16(mod 17), 10≡24≡7 (mod 17),
1010≡2(mod 17), 1011≡20≡3mod 17), 1012≡30≡13(mod 17), 1013≡45≡11(mod 17), 1014≡25≡8(mod 17), 1015≡12(mod 17), 1016≡52≡1(mod 17).
以后开始循环。
111…1=1+10+102 +…+10n ≡1＋1+1+…+1=n+1(mod 9),
1个1个1
所以，当n≡0(mod 9),即9|n时，111…1≡1(mod 9).
个1
2n 111…1=1+10+10 +…+10 ≡1＋10+9+12+3+4+1+10+9+12+3+4+1+…
1个个
=1+39+39+…（mod 13）,所以，6|n时，111…1≡1(mod 13),
1个1
2n 111…1=1+10+10 +…+10
1个1
=1＋10＋15＋14＋4＋6＋9＋5＋16＋7＋2＋3＋13＋11＋8＋12＋1＋…
16个
=1＋136＋…（mod 17）,所以，16|n时，111…1≡1(mod 17).
1个1
为使n最小，n应为9，6，16的最小公倍数，即n=144.
例7 下图3-103的七张卡片中有3张上面的数是未知整数。这3个未知整数都
是3的倍数，并且这3个数的和是180.有三个学生，每人取走2张卡片，各自的两张卡片上的数的和都彼此相同，请问剩下的1张卡片上写的数是几？
图3-103
【解】设三个未知整数分别为x1,x2,x3,那么
34≡46≡61≡79≡1（mod 3）, x1≡x2≡x3≡0(mod 3).
七张卡片上7个数的和为：
34+46＋61＋79＋180=400≡1（mod 3）
由于三个学生每人取走的两张卡片上数的和都是彼此相等，所以，取走的这6张卡片上的数的总和被3整除。因此，剩下的1张卡片上的数是被3除余1.即剩下的卡片上的数是34，46，或79.
若剩下的是标有34的卡片，则每人手中两张卡片数的和为：
（400-34）÷3=122≡2（mod 3）.
这就需要每人取走的两张卡片上的数都应被3除余1，但实际上我们只有四张这样的卡片。因此不可能剩下标有34的卡片。同理，也不可能剩下标有61或79的卡片，经捡验，剩下的卡片上写的数应为46.
例8 在黑板上写数1，2，3，…，1986，1989。然后从所写的数中擦去某些数，同时，写上它们的和除以7的余数，这叫一次操作。若干次操作之后，在黑板上剩下的两个数，其中之一是987，那么剩下的另一个数是几？
【解】设A被7除的余数为rA ，0 ≤rA ＜7.即
A ≡rA (mod 7) .
其中A=1＋2＋…＋1986＋1987=（1+1987）×1987=1987×7×142≡（mod 7）,21
即rA=0.
设第一次擦去的数之和为B，B被7除余数为rB，0≤rB ＜7，即
B≡rB (mod 7) .
①-②得A-B≡rA- rB(mod 7)，即
A-B+ rB ≡rA (mod 7) 。
③式说明操作一次，黑板上数之和仍为被7除余rA.若干次操作之后，设剩下的另一个数是x，则987+x≡rA (mod 7)，即x≡0 (mod 7).
因为987不是除以7的余数，按操作可知，数x就是除以7的余数， 即0≤x＜7，所以x=0.即剩下的另一个数为0.
1.小马虎在座一道有余数的除法时，降被除数237错写成273，计算出结果商比正确答案多3，而余数恰好相同。请问这道题的除数是几？
2.甲、乙、丙三数分别为603，939，393，某数A除甲数所得余数是A除乙数所得余数的两倍，A除乙数所得余数是A除丙数所得余数的两倍，则A等于几？
3.31001×71002×131003×171004的个位数字是几？
4.1986年春节（2月9日）是星期日，问2005年的六一儿童节是星期几？ 5. 1010＋1010＋1010＋…＋1010除以7的余数。
12310
6.证明：19911991＋19921992不是平方数。
7.把由1开始的正整数依次写下去，一直写到第189位上，[**************]13…，那么，这个数用9除的余数是多少？
20048.2004写成一个多位数后，它的数字之和为A，A的数字之和为B，B的数字之和为C，求C。
9.一支总人数是5的倍数，且不少于1000热播的游行队伍，若按每横排4热播编队，最后是3人；若每横排3人编队，最后是2人；若每横排2人编队，最后是1人。求这支队伍至少有多少人？
10.n是使111…1被1989除余1的最小的正整数n.
1
（1）p=11…1 99…9 88…8 99…9被1989除余数是几？
n个1 n个9 n个8 n个9
（2） q=111…1被1989除余数是几？
11.在一张纸上连续写下：[**************]9…321.把第一个数字1乘2加上第2个数字9，然后再乘2加上第三个数字9，再乘2加上第四个数字2，……，一直加到最后一个数字1，得到一个新数，这叫一个操作。若干次操作之后，得到一个一位数，请问这个一位数是几？