因为7≡1mod8，所以即A被9除的余数等于它的各位数字之和被9除的余数．说明1特别地，一个数能被9整除的充要条件是它的各位数字之和能被9整除．2算术中的“弃九验算法”就是依据本题的结论．例6任意平方数除以4余数为0和1这是平方数的重要特征．证因为奇数2k＋14k＋4k1≡1mod4，偶数2k4k≡0mod4，所以
222222
7
2
＋1
≡1
2
＋1
＝1mod8，
7即余数为6．例9形如
2
＋1
1≡2≡6mod8，
F
＝21，
0，1，2，的数称为费马数．证明：当
≥2时，F
的末位数字是7．证当
≥2时，2是4的倍数，故令24t．于是F
2＋12116＋1≡6＋1≡7mod10，即F
的末位数字是7．说明费马数的头几个是F0＝3，F1＝5，F2＝17，F3＝257，F4＝65537，
t2
4tt

2

例7任意平方数除以8余数为0，1，4这是平方数的又一重要特征．证奇数可以表示为2k＋1，从而奇数4k＋4k14kk＋11．因为两个连续整数k，k＋1中必有偶数，所以4kk＋1是8的倍数，从而奇数8t1≡1mod8，偶数2k4kk为整数．1若k偶数2t，则4k16t＝0mod8．2若k奇数2t1，则4k42t＋116t＋t4≡4mod8，所以
22222222222
它们都是素数．费马便猜测：对所有的自然数
，F
都是素数．然而，这一猜测是错误的．首先推翻这个猜测的是欧拉，他证明了下一个费马数F5是合数．证明F5是合数，留作练习．利用同余还可以处理一些不定方程问题．例10证明方程xy25z没有整数解．证对于任一整数x，以5为模，有x≡0，±1，±2mod5，x≡0，1，4mod5，x≡0，1，1mod5，即对任一整数x，x≡0，1mod5．同样，对于任一整数yy≡0，1mod5，
444244
求余数是同余的基本问题．在这种问题中，先求出与±1同余的数是一种基本的解题技巧．例81求33除22求8除7
2
11998
所以xy2≡2，3，4mod5，从而所给方程无整数解．说明同余是处理不定方程的基本方法，但这种方法也非常灵活，关键在于确定所取的模本例我们取模5，这往往应根据问题的特点来确定．
4
4
的余数．
1的余数．
解1先找与±1mod33同余的数．因为2＝32≡1mod33，所以2≡1mod33，2
1998105
222≡8≡25mod33，
10199
5
3
f练习二十五1．求证：17｜19
1000
6．今天是星期天，过3天是星期几？再过5几？
100
1998
天又是星期
1．
2．证明：对所有自然数
，330｜6511．
2

2

7．求
1×3×5×7××1999的末三位数字．
8．证明不定方程xy8z6无整数解．
2
2
4．求2
1000
除以13的余数．
5．求1＋2＋3r