初中数学竞赛第七节带余除法（含答案）

第七节 带余除法

内容讲解

用一个整数a去除整数b，且a>0，则必有并且只有两个整数q与r，使b=aq+r，?0≤r

b，b不能被a整除，或者说，b除以a有余数．

利用余数将自然数分类，在解决实际问题中有广泛应用．我们说，任何一个自然数b被正整数a除时，余数只可能是0、1、2、…、a-1．这样就可以把自然数分为a类．例如，一个自然数被4除，余数只能是0、1、2、3中的一个．因此，所有自然数按被4除时的余数分为4类，即4k，4k+1，4k+2，4k+3．任何自然数都在这四类之中．

我们还关心带余除法中的另一个问题，即是当两个整数a、b去除不为0?的同一整除n时，余数相同，称为同余问题．一般地，记为a≡b（mod n）．记号“≡”读作“同余于”，“mod”读作“模”，此式读作“a同余于b模n”或“a与b对模n?同余”． 例如：32≡7（mon 5），是由于32与7分别被5除，余数都是2．读作“32与7对模5同余”．

在同余问题中，常用的性质有： （1）同一模的同余式可以相加，就是 如果a1≡b1（mod n），a2≡b2（mod n）， 那么a1+a2≡b1+b2（mod n）． （2）同一模的同余式可以相乘，就是 如果a1≡b1（mod n），a2≡b2（mod n）， 那么a1a2≡b1b2（mod n）．

（3）同余式双方可乘以同一整数，就是

如果a≡b（mod n），对于任何整数k，那么ak≡bk（mod n）．

（4）同余式双方可“约去”一个共同的因子（与模数互质的因数）．就是

- 1 -

如果a≡b（mod n），a1q=a，b1q=b，q与n互质，那么a1≡b1（mod n）． 例题剖析

例1 求1273×465的积，被7除的余数．

分析：直接用7去除1273×465的积，计算太麻利，利用带余除去的一般表达式去做，可简化运算．

解：设1273×465的积被7除，商p，余数r． 得1273×465=7p+r （1） 又∵1273=7a+6，465=7b+3． ∴1273×465=（7a+6）（7b+3） =7（7ab+3a+6b+2）=4 （2） 比较（1）、（2），得r=4．

评注：求余数，对式中的商q、a、b是多少，我们并不关心．?实际要做的是找到余数6和3，求出6×3=18，除以7的余数4． 例2 求1313+1414+1515被13除的余数．

分析：直接计算求余数非常困难．因为13│1313，所以只需算1414+1515被13除的余数．?注意到14÷13余1，15÷13余2，利用同余性质，问题可大大简化． 解：∵1313能被13整除，余数为0． 而14≡1（mod 13），15≡2（mod 13）． 由同余性质（2），得14≡114≡1（mod 13）， 1515≡215≡8（mod 13）．

由同余性质（1），得1313+1414+1515≡0+1+8≡9（mod 13）． 即1313+1414+1515被13除的余数为9．

评注：利用同余式的性质求余数，使求余数的问题大大简化．

例3 两整数a、b，a除以7余2，b除以7余5，当a2>3b时，求a2-3b的差除以7的余数．

- 2 -

分析：利用带余除法的一般表达式，代入式子a2-3b中，?经过变形就可得到所求的余数．

解：设a=7m+2，b=7n+5， 当a2>3b时，a2-3b>0．

∴a2-3b=（7m+2）2-3（7n+5）=49m2+28m+4-21n-15=7（7m2+4m-3n-2）+3． 得a2-3b除以7余3．

评注：变形a2-3b的目标，就是将它写成带余除法的一般式b=aq+r，?而我们关心的只是式中的r值．

例4 求x（0≤x<100），使x≡14（mon 15），且x≡5（mod 8）．

分析：所求的x是不小于0且小于100的整数，x满足被15去除余14，被8去除余5，根据这两个条件，容易找出整数x．

解：∵0≤x<100，满足x≡14（mod 15）的整数有14、29、44、59、74、89； 满足x≡5（mod 8）的整数有5、13、21、29、37、45、53、61、69、77、85?、?93． 则同时满足上述两个条件的只有x=29．

评注：注意到满足条件的各个数，依次相差的就是“模数”，找出这些数以及同时满足两个条件的数，就不困难了．

例5 今有物，不知其数，三三数之，剩二；五五数之，剩三；七七数之，?剩二，问物几何？

分析：本问题是有一个数，被3除余2，被5除余3，被7除余2，求此数．利用带余除法表达式表示这个数，然后求出各除数3、5、7的最小公倍数105，再令与105?相乘的数为0，就可得到满足条件的最小整数． 解：设这堆物为x，根据题意，得 x=3a+2，x=5b+3，x=7c+2．

∵3×5×7=105，且3、5、7互质，所以最小公倍数为105．

- 3 -

?35x?105a?70,(1)? 上三式变形为?21x?105b?63,(2)

?15x?105c?30.(3)? 由（2）+（3）-（1），得x=105（b+c-a）+23． 取b+c-a=0，则x=23．

评注：这是我国古代一个典型的余数问题．这类问题通常是先求出各除数的最小公倍数，然后写出要求数的表达式．当出现加上一个常数，?就可取与最小公倍数相乘的这个数为0；当出现减去一个常数，可取这个乘数为1，另外，x=23只不过是满足本例条件的最小正整数而已．

巩固练习 1．填空题：

（1）2006年“五一节”是星期一，同年“国庆节”是星期_________； （2）有一个数能被5整除，但除以4余3，这个正整数最小是________； （3）一个整数去除300，262，205，所得余数相同，这个整数是_______； （4）一个数除以3余2，除以4余1，那么这个数除以12，余数是______； （5）正整数32006+42006除以3，所得余数是________．

2．求一个最大的数，用它去除13511，13903与14589，所得余数相同．

3．求x（0≤x<20），使x≡2（mod 3）且x≡1（mod 4）．

- 4 -

4．所有大于40，小于80的两位数中，找出用3和7去除，都余2的数．

5．证明：如果两个整数被同一正整数去除时，所得余数相等，?那么这两个整数相减

的差，一定能被这个正整数整除．

6．一个两位整数被7除余4，被3除余1，求满足条件的两位数．

7．有一个六位数能被11整除，首位数字是3，其余各位数字都不相同，求满足条件的最小的六位数．

8．求证：任何一个不小于24的自然数，都可以由若干个5和7相加而得．

- 5 -

答案:

1．（1）星期日；（2）15；（3）19；（4）5；（5）1；（6）72≡37（mod 7） 2．98 3．5或17

4．44、65 5．设a=np+r，b=nq+r，则a-b=n（p-q），即n│（a-b）． 6．满足条件的两位数有25，46，67，88．

7．最小六位数301245， ∵（3+1+4）-（0+2+5）=1，

∴改5为6，得满足条件的最小六位数301246． 8．n=24=2×7+2×5；n>24，

设n=5k+r（k≥5），分r=0，1，2，3，4几种情况讨论可得证．

- 6 -

答案:

1．（1）星期日；（2）15；（3）19；（4）5；（5）1；（6）72≡37（mod 7） 2．98 3．5或17

4．44、65 5．设a=np+r，b=nq+r，则a-b=n（p-q），即n│（a-b）． 6．满足条件的两位数有25，46，67，88．

7．最小六位数301245， ∵（3+1+4）-（0+2+5）=1，

∴改5为6，得满足条件的最小六位数301246． 8．n=24=2×7+2×5；n>24，

设n=5k+r（k≥5），分r=0，1，2，3，4几种情况讨论可得证．

- 6 -

本文来源：https://www.bwwdw.com/article/uhf7.html