鼎吉教育（Dinj Education）中小学生课外个性化辅导中心资料 初中数学竞赛专题培训讲练
初中数学竞赛专题培训 第二十五讲* 同余式
数论有它自己的代数，称为同余理论．最先引进同余的概念
与记号的是数学王子高斯．
先看一个游戏：有n＋1个空格排成一行，第一格中放入一枚棋子，甲乙两人交替移动棋子，每步可前移1，2或3格，以先到最后一格者为胜．问是先走者胜还是后走者胜？应该怎样走才能取胜？
取胜之道是：你只要设法使余下的空格数是4的倍数，以后你的对手若走i格(i=1，2，3)，你走4-i格，即每一次交替，共走了4格．最后只剩4个空格时，你的对手就必输无疑了．因此，若n除以4的余数是1，2或3时，那么先走者甲胜；若n除以4的余数是0的话，那么后走者乙胜．
在这个游戏里，我们可以看出，有时我们不必去关心一个数是多少，而要关心这个数用m除后的余数是什么．又例如，1999年元旦是星期五，1999年有365天，365=7×52＋1，所以2000年的元旦是星期六．这里我们关心的也是余数．这一讲中，我们将介绍同余的概念、性质及一些简单的应用． 同余，顾名思义，就是余数相同．
定义1 给定一个正整数m，如果用m去除a，b所得的余数相同，则称a与b对模m同余，记作
a≡b(modm)，
并读作a同余b，模m．
若a与b对模m同余，由定义1，有
a=mq1＋r，b=mq2+r．
所以 a-b=m(q1-q2)， 即 m｜a-b． 反之，若m｜a-b，设
a=mq1＋r1，b=mq2＋r2，0≤r1，r2≤m-1，
则有m｜r1-r2．因｜r1-r2｜≤m-1，故r1-r2=0，即r1＝r2． 于是，我们得到同余的另一个等价定义：
定义2 若a与b是两个整数，并且它们的差a-b能被一正整数m整除，那么，就称a与b对模m同余．
同余式的写法，使我们联想起等式．其实同余式和代数等式有一些相同的性质，最简单的就是下面的定理1． 定理1 (1)a≡a(modm)．
(2) 若a≡b(modm)，则b≡a(modm)．
约去5得
5≡1(mod 10)．
这显然是不正确的．但下面这种情形，相约是可以的． 定理3 若ac≡bc(modm)，且(c，m)=1，则 a≡b(modm)． 证 由题设知
ac-bc=(a-b)c=mk．
由于(m，c)=1，故m｜a-b，即a≡b(modm)． 定理4 若n≥2，
a≡b(modm1)， a≡b(modm2)， ???? a≡b(modmn)，
且M=[m1，m2，?，mn]表示m1，m2，?，mn的最小公倍数，则
a≡b(modM)．
前面介绍了同余式的一些基本内容，下面运用同余这一工具去解决一些具体问题． 即
a±c≡b±d(modm)，ac≡bd(modm)．
由此我们还可以得到：若a≡b(modm)，k是整数，n是自然数，则
a±k≡b±k(modm)， ak≡bk(modm)，a≡b(modm)．
对于同余式ac≡bc(modm)，我们是否能约去公约数c，得到一个正确的同余式a≡b(modm)？
在这个问题上，同余式与等式是不同的．例如
25≡5(mod 10)，
n
n
(3) 若a≡b(modm)，b≡c(modm)，则a≡c(modm)． 在代数中，等式可以相加、相减和相乘，同样的规则对同余式也成立．
定理2 若a≡b(modm)，c≡d(modm)，则 a±c≡b±d(modm)，ac≡bd(modm)． 证 由假设得m｜a-b，m｜c-d，所以
m｜(a±c)-(b±d)， m｜c(a-b)＋b(c-d)，
学习地址：佛山市南海区南海大道丽雅苑中区雅广居2 D 第1页 咨询热线：0757-86307067 13760993549（吉老师）
鼎吉教育 遵循：“授人以鱼，不如授人以渔”的教育理念 秉承：以人为本，质量第一，突出特色， 服务家长
应用同余式的性质可以简捷地处理一些整除问题．若要证明m整除a，只需证a≡0(modm)即可． 例1 求证： (1)8｜(55
2n
1999
803≡261(mod 271)， 464≡193(mod 271)，
所以
＋17)；
(2) 8(3＋7)； (3)17｜(19
1000
-1)．
1999
≡-1(mod 8)，55
1999
证 (1)因55≡-1(mod 8)，所以55≡-1＋17=16≡0(mod 8)，于是8｜(55
2
2n
＋17
故271｜A．因(7，271)=1，所以1897整除A．
例4 把1，2，3?，127，128这128个数任意排列为a1，a2，?，a128，计算出
｜a1-a2｜，｜a3-a4｜ ，?，｜a127-a128｜，
1999
＋17)．
2n
(2)3=9≡1(mod 8)，3≡1(mod 8)，所以3＋7≡1＋7≡0(mod 8)，即8｜(3＋7)．
(3)19≡2(mod 17)，19≡2=16≡-1(mod 17)，所以19
1000
4
4
2n
再将这64个数任意排列为b1，b2，?，b64，计算
｜b1-b2｜，｜b3-b4｜，?，｜b63-b64｜．
如此继续下去，最后得到一个数x，问x是奇数还是偶数？ 解 因为对于一个整数a，有
｜a｜≡a(mod 2)， a≡-a(mod 2)，
所以
=(19)250≡(-1)250≡1(mod 17)，于是
17｜(19
n
1000
4
-1)．
例2 求使2-1为7的倍数的所有正整数n．
解 因为2≡8≡1(mod 7)，所以对n按模3进行分类讨论． (1) 若n=3k，则
2-1＝(2)-1＝8-1≡1-1＝0(mod 7)；
(2) 若n=3k＋1，则
2-1=2·(2)-1=2·8-1 ≡2·1-1＝1(mod 7)；
(3) 若n=3k＋2，则
2-1=2·(2)-1=4·8-1 ≡4·1-1＝3(mod 7)．
所以，当且仅当3｜n时，2-1为7的倍数． 例3 对任意的自然数n，证明
A=2903-803-464＋261
能被1897整除．
证 1897=7×271，7与271互质．因为
2903≡5(mod 7)， 803≡5(mod 7)， 464≡2(mod 7)， 261≡2(mod 7)，
所以
A=2903-803-464+261 ≡5n-5n-2n+2n=0(mod 7)，
故7｜A．又因为
2903≡193(mod 271)，
n
n
n
n
n
n
n
n
nk
n
2
3
k
k
k
n
3k
k
n
3
k
k
k
3
b1＋b2＋?＋b64
=｜a1-a2｜+｜a3-a4｜+?+｜a127-a128｜ ≡a1-a2＋a3-a4+?+a127-a128
≡a1＋a2＋a3＋a4+?+a127＋a128(mod 2)，
因此，每经过一次“运算”，这些数的和的奇偶性是不改变的．最终得到的一个数
x≡a1＋a2＋?＋a128＝1＋2＋?＋128 ＝64×129≡0(mod 2)， 故x是偶数．
如果要求一个整数除以某个正整数的余数，同余是一个有力的工具．另外，求一个数的末位数字就是求这个数除以10的余数，求一个数的末两位数字就是求这个数除以100的余数． 例5 求证：一个十进制数被9除的余数等于它的各位数字之和被9除的余数．
10≡1(mod 9)，
故对任何整数k≥1，有
10≡1＝1(mod 9)．
因此
k
k
◆ 以鲜明的教育理念启发人 ◆ 以浓厚的学习氛围影响人 第2页 ◆ 以不倦的育人精神感染人 ◆ 以优良的学风学纪严律人◆
鼎吉教育（Dinj Education）中小学生课外个性化辅导中心资料 初中数学竞赛专题培训讲练
所求余数为25．
(2)因为7≡-1(mod 8)，所以
即A被9除的余数等于它的各位数字之和被9除的余数． 说明 (1)特别地，一个数能被9整除的充要条件是它的各位数字之和能被9整除．
(2)算术中的“弃九验算法”就是依据本题的结论． 例6 任意平方数除以4余数为0和1(这是平方数的重要特征)． 证 因为
奇数=(2k＋1)=4k＋4k+1≡1(mod 4)，
偶数=(2k)=4k≡0(mod 4)，
所以
2
2
2
2
2
2
7
2n＋1
≡(-1)
2n＋1
＝-1(mod 8)，
7
即余数为6． 例9 形如
2n＋1
-1≡-2≡6(mod 8)，
Fn＝2+1，n=0，1，2，?
的数称为费马数．证明：当n≥2时，Fn的末位数字是7． 证 当n≥2时，2是4的倍数，故令2=4t．于是
Fn=2＋1=2+1=16＋1 ≡6＋1≡7(mod 10)，
即Fn的末位数字是7． 说明 费马数的头几个是
t2n
4t
t
n
n
2n
例7 任意平方数除以8余数为0，1，4(这是平方数的又一重要特征)．
证 奇数可以表示为2k＋1，从而
奇数=4k＋4k+1=4k(k＋1)+1．
因为两个连续整数k，k＋1中必有偶数，所以4k(k＋1)是8的倍数，从而
奇数=8t+1≡1(mod 8)， 偶数=(2k)=4k(k为整数)．
(1)若k=偶数=2t，则
4k=16t＝0(mod 8)．
(2)若k=奇数=2t+1，则
4k=4(2t＋1)=16(t＋t)+4≡4(mod 8)，
所以
2
2
2
2
2
2
2
2
22
2
F0＝3，F1＝5，F2＝17，F3＝257，F4＝65537，
它们都是素数．费马便猜测：对所有的自然数n，Fn都是素数．然而，这一猜测是错误的．首先推翻这个猜测的是欧拉，他证明了下一个费马数F5是合数．证明F5是合数，留作练习． 利用同余还可以处理一些不定方程问题． 例10 证明方程
x+y+2=5z
没有整数解．
证 对于任一整数x，以5为模，有
x≡0，±1，±2(mod 5)， x≡0，1，4(mod 5)， x≡0，1，1(mod 5)，
即对任一整数x，
x≡0，1(mod 5)．
同样，对于任一整数y
442
4
4
求余数是同余的基本问题．在这种问题中，先求出与±1同余的数是一种基本的解题技巧． 例8 (1)求33除2 (2)求8除7
2n+1
1998
4
4
y≡0，1(mod 5)，
所以 x+y+2≡2，3，4(mod 5)， 从而所给方程无整数解．
说明 同余是处理不定方程的基本方法，但这种方法也非常灵活，关键在于确定所取的模(本例我们取模5)，这往往应根据问题的特点来确定．
4
的余数．
-1的余数．
解 (1)先找与±1(mod 33)同余的数．因为
2＝32≡-1(mod 33)，
所以 2≡1(mod 33)，
2
199810
5
=(2)·2·2≡-8≡25(mod 33)，
1019953
学习地址：佛山市南海区南海大道丽雅苑中区雅广居2 D 第3页 咨询热线：0757-86307067 13760993549（吉老师）
鼎吉教育 遵循：“授人以鱼，不如授人以渔”的教育理念 秉承：以人为本，质量第一，突出特色， 服务家长
练习二十五
1．求证：17｜(191000
-1)．
2．证明：对所有自然数n，330｜(62n
-52n
-11)．
4．求21000
除以13的余数．
5．求15
＋25
＋35
＋?＋995
＋1005
除以4所得的余数．
◆ 以鲜明的教育理念启发人 ◆ 以浓厚的学习氛围影响人 6．今天是星期天，过3100天是星期几？再过51998
天又是星期
几？
7．求n=1×3×5×7×?×1999的末三位数字．
8．证明不定方程x2
+y2
-8z=6无整数解．
第4页 ◆ 以不倦的育人精神感染人 ◆ 以优良的学风学纪严律人◆