ab，即a≡bmodm．定理4若
≥2，a≡bmodm1，a≡bmodm2，a≡bmodm
，且Mm1，m2，，m
表示m1，m2，，m
的最小公倍数，则a≡bmodM．前面介绍了同余式的一些基本内容，下面运用同余这一工具去解决一些具体问题．


f应用同余式的性质可以简捷地处理一些整除问题．若要证明m整除a，只需证a≡0modm即可．例1求证：18｜55
2
1999
803≡261mod271，464≡193mod271，所以
＋17；
283＋7；317｜19
1000
1．
1999
证1因55≡1mod8，所以55≡1＋1716≡0mod8，于是8｜55
22

≡1mod8，55
1999
＋17
故271｜A．因7，2711，所以1897整除A．例4把1，2，3，127，128这128个数任意排列为a1，a2，，a128，计算出｜a1a2｜，｜a3a4｜，，｜a127a128｜，
1999
＋17．
2

239≡1mod8，3≡1mod8，所以3＋7≡1＋7≡0mod8，即8｜3＋7．319≡2mod17，19≡216≡1mod17，所以19
1000442

再将这64个数任意排列为b1，b2，，b64，计算｜b1b2｜，｜b3b4｜，，｜b63b64｜．如此继续下去，最后得到一个数x，问x是奇数还是偶数？解因为对于一个整数a，有｜a｜≡amod2，a≡amod2，所以
19250≡1250≡1mod17，于是17｜19
1000
4
1．
例2求使21为7的倍数的所有正整数
．解因为2≡8≡1mod7，所以对
按模3进行分类讨论．1若
3k，则21＝21＝81≡11＝0mod7；2若
3k＋1，则21221281≡211＝1mod7；3若
3k＋2，则21221481≡411＝3mod7．所以，当且仅当3｜
时，21为7的倍数．例3对任意的自然数
，证明A2903803464＋261能被1897整除．证18977×271，7与271互质．因为2903≡5mod7，803≡5mod7，464≡2mod7，261≡2mod7，所以A2903803464261




k
23kkk
3kk
3kkk3
b1＋b2＋＋b64｜a1a2｜｜a3a4｜｜a127a128｜≡a1a2＋a3a4a127a128≡a1＋a2＋a3＋a4a127＋a128mod2，因此，每经过一次“运算”，这些数的和的奇偶性是不改变的．最终得到的一个数x≡a1＋a2＋＋a128＝1＋2＋＋128＝64×129≡0mod2，故x是偶数．如果要求一个整数除以某个正整数的余数，同余是一个有力的工具．另外，求一个数的末位数字就是求这个数除以10的余数，求一个数的末两位数字就是求这个数除以100的余数．例5求证：一个十进制数被9除的余数等于它的各位数字之和被9除的余数．
10≡1mod9，故对任何整数k≥1，有10≡1＝1mod9．因此
kk
≡5
5
2
2
0mod7，故7｜A．又因为2903≡193mod271，
f所求余数为25．2r