第3讲带余除法和同余知识网络一般地，整数a被自然数b除，必定有惟一的整数q和惟一的整数r，使得a=b×q+r其中r＜b，当r=0时，就是整除的形式。同样，可以把上式转化为a-r=b×q这样也可以看成（a-r）是b的倍数。同样，就可以引出同余的定义。如果a、b为整数，n为正整数，a、b被n除所得的余数相同，就称a、b对模n同余，并用符号a≡bmod(n)来表示。如果a、b对模n同余，那么定有a-b是n的倍数。重点·难点本讲的重点难点在于对同余的应用，这就要首先掌握同余的几个基本性质：对a、b、c、d均为整数，m、n为正整数，有（1）a≡amod(n)。（2）如果a≡bmod(n)，那么b≡amod(n)。（3）如果a≡bmod(n)及b≡cmod(n)，那么a≡cmod(n)。（4）如果a≡bmod(n)，c≡dmod(n)，那么a+c≡(b+d)mod(n)。（5）如果a≡bmod(n)，c≡dmod(n)，那么a×c≡b×dmod(n)。（6）如果a≡bmod(n)，那么。学法指导带余除法的题一般数字较大、直接计算有难度，如何化繁为简就成为关键。一般地，只要对题目有深入的分析，抓住隐藏在其中的规律，就能顺利解出题来。、经典例题[例1]我国古代数学名著《孙子算经》有这样一道有关自然数的题目：今有物不知其数，三三数之剩2，五五数之剩3，七七数之剩2。问物几何？翻译成现代文就是：一个数被3除余2，被5除余3，被7除余2。求这个数。思路剖析设这个数为a，则有a≡2mod(3)，a≡3mod(5)，a≡2mod(7)可以取易得，是整数易得是整数易得是整数因此解答由上述分析因此这个数最小值是23。[例2]菲波那契数列定义如下：前两个数都是1，从第三个数起，每个数是前面两个数的和。于是其中前面几个数是1，1，3，5，8，13，21，34，55⋯（1）求其中第2002个数被4除的余数。（2）如果在前n个数中有2002个是4的倍数，问n应是多少？思路剖析我们只需考虑菲波那契数列的前两个数被4除的余数，后面其他数被4除的余数可根据菲波那契数列的构成规律得到。例如：第一个数1被4除余1，第二个数1被4除余1，那么第三个数被4除的余数就是前两个余数的和，被4除的余数为2，第四个数被4除的余数就是第二个数被4除的余数1与第三个数被4除的余数2的和，被4除的余数为3。因此菲波那契数列中前若干个数被4除的余数依次为：1，1，2，3，1，0，1，1，2，3，1，0⋯可以发现其中的规律是每6位是循环重复的，到此问题便可解决。解答（1）由于2002=6×333+4，而第四个余数是3，所以第2002个数被4除余3。（2）由于每六个数中有1个是4的倍数，所以n=6×2002=12012，即前12012个数中有2002个数是4的倍数。[例3]将自然数1，2，3，⋯排成如下的表，求2002这个数在第几行，第几列？第1列第2列第3列第4列第5列第6列第1行12345第2行109876第3行1112131415第4行2019181716⋯⋯⋯⋯⋯思路剖析表中的数依次按第2，3，4，5，6，5，4，3，2，1列循环排列，并且每一行有五个数。所以数字的列数应该与除以10所得余数有关，行数与除以5所得商有关。解答2002=200×10+2；所以2002所在列数与2所在列数是一样的，因此2002位于第3列。2002=400×5+2；所以2000应该在第400行，从而2002位于第401行。综上所述，2002位于此表中第401行第3列。[例4]求19790422与22409791的乘积被7除后的余数。思路剖析这是两上比较大的数，因此不宜算出乘积，再除以7求余数。考虑利用同余的基本性质（5）。解答19790422=2827203×7+1，即19790422≡1mod(7)同理22409791=3201398×7+5，即22409791≡5mod(7)从而19790422×22409791被7除所得的余数为5。[例5]把1到2002这2002个自然数依次写下来，得到一个多位数1234567891011⋯20012002，试求这一多位数除以9的余数。思路剖析从一个数被9除的特征可以知道，一个自然数除以9的余数，与这个自然数各个数位上的数位和除以9的余数正好相同。如此一来，求一个多位数除以9的余数就转化为1到2002这2002个自然数中，所有数字之和是多少的问题。但这还不够，有这样一个规律：一个多位数被9除的余数，可以根据情况在适当的地方把这个多位数断开，然后把每一段的数加起来，这个和被9除的余数，就是这个多位数被9除的余数。解答我们可以把多位数1234567891011⋯20012002断开1，2，3，4，⋯，2001，2002，而1+2+3+4+⋯+2001+2...
