1.2带余除法

带余除法

我们知道两个整数的和、差、积仍然是整数，但是用一不等于零的整数去除另一个整数所得的商却不一定是整数，因此我们引进整除的概念；

定义 设a,b是任意两个整数，其中b?0，如果存在一个整数q使得等式

a?bq ?1? 成立，我们就说b整除a或a被b整除，记作b|a，此时我们把b叫作a的因数，把a叫作b的倍数.

如果?1?里的整数q不存在，我们就说b不能整除a或a不被b整除，记作b？a.

整除这个概念虽然简单，但却是数论中的基本概念，我们很容易从定义出发，证明下面那些关于可除性的基本定理.

定理1 若a是b的倍数，b是c的倍数，则a是c的倍数，也就是

b趑a,cb?c a.

a,c就是说存在两个整数b证 b趑b1，a1使得

a=a1b,b=b1c

成立，因此

a=?a1b1?c.

a. 证完 但a1b1是一个整数，故c? 定理2 若a,b都是m的倍数，则a?b也是m的倍数.

证 a,b是m的倍数的意义就是存在两个整数a1,b1，使得

a=a1m,b=b1m

因此

a?b=?a1?b1?m,

但a1?b1是整数，故a?b是m的倍数. 证完

用同样的方法，可以证明

定理3 若a1,a2,?,an都是m的倍数，q1,q2,?,qn是任意n个整数，则q1a1+q2a2+?

+qnan是m的倍数.（证明留给读者.）

上面我们仅就能够整除的情形初步地讨论了一下，至于在一般情形下，我们有下面很重要的 定理4（带余除法） 若a,b是两个整数，其中b>0，则存在着两个整数q及r，使得

a=bq+r,0?r

证 作整数序列

?,-3b,-2b,-b,0,b,2b,3b,?

则a必在上述序列的某两项之间，即存在一个整数q使得

qb?a

成立，令a-qb=r，则a=bq+r，而0?r

设q1,r1是满足?2?的两个整数，则

a=bq1+r1,0?r1

因而 bq1+r1=bq+r. 于是 b?q?q1?=r1-r. 故 bq?q1=r1?r.

由于r及r1都是小于b的正数，所以上式右边是小于b的.如果q?q1则上式左边?b.这是不可能的.因此q=q1而r=r1.

证完

整数的很多基本性质，都可以从定理4引导出来.我们可以说这一章最重要的部分是建立在定理4的基础上的.

定义 ?2?中的q叫作a被b除所得的不完全商，r叫作a被b除所得到的余数. 为了更好地了解这个定义，我们举例说明一下： 例 设b=15，则当a=255时

a=17b+0,r=0<15，而q=17；

当a=417时

a=27b+12,0

当a=-81时，

a=-6b+9,0

例 找规律判定“300”位于哪个字母的下边.（美国89年小学数学奥赛题）

A B C D E F G1 2 3 4 5 6 78 9 10 11 12 13 1415 16 ? 解： 观察可以发现，两行7个数组成一组，故300=7?2+6与6同在D的下边. 练习题：

1.如果按红、橙、黄、绿、青、蓝、紫的顺序，将19921992技1992只彩灯依次反

1991个1992 复排列，那么_____颜色的彩灯必定要比其他颜色的彩灯少一只.

解： 紫.考虑通过试除发现规律后求彩灯总数被7除的余数即可.经试除得:

199219921992能被7整除,而1991被3除余2,所以彩灯总数与19921992被7除的余数相同,均为6.所以,紫色的彩灯要比其它颜色的彩灯少一只.

2. 从7开始,把7的倍数依次写下去,一直写到994成为一个很大的数: 71421??987994.

这个数是_____位数.

解：411.97?1?2 ?一位数中能被7整除的数有1个 997?14?1 ?两位数中能被7整除的数有（14?1?）13个 所以，这个数的位数为 1 ?

9997?142?5?三位数中能被7整除的数有142?13?1?128（个）??3．幼儿园某班学生做游戏，如果每个学生分得的弹子一样多，弹子就多12颗，如果再增加12颗弹子，那么每个学生正好分得12颗，问这班有多少个学生？原有多少颗弹子？

解：依题意知，原来每个学生分相等的若干颗，余12颗，则学生人数大于12.同时由增加12颗后每个学生正好分得12颗,即12?12?24(颗),24能被班级人数整除,又24能分解为 ????由班级人数大于可知符合题意的是人.所以,共有弹子数1224?12?276(颗).

4．已知：a?199119911991??1991,问：a除以13,余数是几？ 1991个1991

解：用试除的方法可知:199119911991可以被13除尽原数.a有1991个 1991.因为1991除以3余2,所以a与19911991除以13所得余数相同. 又19911991除以13余8,所以a除以13的余数也是8.5100．个7组成的一百位数,被13除后,问： ?1?余数是多少？ ?2?商数中各位数字之和是多少？

解：因为 77777713?59829,即777777能被13整除,把这100个7,从第一个起,每6个 分成一组,1006?16?4，共16组还多4个.每一组除以13的商都是59829,7777 除以13的商是598,余数是3.所以,100个7组成一百位数除以13后,余数是3,商数 中各位数字之和是 ?5?9?8?2?9??16??5?9?8?5506．有一个数,甲将其除以8,乙将其除以9.甲所得的商数与乙所得的余数之和为13.试求 甲所得的余数.

解：设甲所得的商和余数分别为a和b,乙所得的商和余数分别为c和d,于是 由题意知8a?b?9c?d,a?d?13.将d?13?a代入前一式并整理后即得 9(a?c)?13?b上式左端是9的倍数,因此13?b也是9的倍数由于.b是被8 除的余数,所以b介于0与7之间故.b?4.

7. 四位数898能同时被17和19整除,那么这个四位数所有质因数的和是_____. 解：51.由17与19互质可知,898能被(17′19?)323整除.因为

8098?323?25?23，

根据商数与余数符合题意的四位数应是323的26倍，所以这个四位数是8398.将8398分解质因数.

26?213创1719 8398?323创所以,这个四位数的所有质因数之和是 2?13?17?19?51.

8. 一串数1、、、247、11、16、22、29??这串数的组成规律，第2个数 比第1个数多1；第3个数比第2个数多2；第4个数比第3个数多3； 依此类推；那么这串数左起第1992个数除以5的余数是_____.解：2.设这串数为a1,a2,a3,?，a1992，?，依题意知

a1?1a2?1?1a3?1?1?2a4?1?1?2?3a5?1?1?2?3?4??a1992?1?1?2?3???1991?1?996199119915?398?1，所以996′1991的积除以5余数为1，因为9965?199?1，1+996 1991除以5的余数是2.

因此,这串数左起第1992个数除以5的余数是2.

9. 222??22除以13所得的余数是_____. 2000个 解：9.因为

222222?2′111111 ?2创1111001 ?2创1117创1113所以222222能被13整除. 又因为2000?6′333?2 222?2?222?200?22

2000个 1998个 22?13?1?9

所以要求的余数是9.

10. 小明往一个大池里扔石子,第一次扔1个石子,第二次扔2个石子,第三次扔3个石子,第四次扔4个石子??，他准备扔到大池的石子总数被106除，余数是0止，那么小明应扔_____次.

解：52.设小明应扔n次,根据高斯求和可求出所扔石子总数为

11?2?3???n?n′(n?1)

21依题意知n′(n?1)能被106整除,因此可设

2

1n′(n?1)?106a即n′(n?1)?212a 2253a, 又212a?2创2a?52 (或54). 根据n与n?1为两个相邻的自然数,可知2创2a?52时, a?13. 当2创12a?54时, a?13,a不是整数,不符合题意舍去. 当2创2因此, n创(n?1)?5253?52??521?,n?52,所以小明扔52次.

11. 七位数372的末两位数字是_____时,不管十万位上和万位上的数字是

0,1,2,3,4,5,6,7,8,9中哪一个,这个七位数都不是101的倍数.

解：76.假设十万位和万位上填入两位数为x,末两位上填入的数为y,(十位上允许是0),那么这个七位数可以分成三个部分3007200?10000x+y,3007200除以101的余数是26, 10000x除以101的余数为x,那么当x+y+26的和是101的倍数时,这个七位数也是101的倍数.如:当y=1时, x=74；当y=2时，x=73，??，而当y=76时，

x=100，而0?x?99，x不可能是100，所以y也不可能是76.由此可知末两位数字

是76时,这个七位数不管十万位上和万位上的数字是几,都不是101的倍数.

12. 有一个自然数,用它分别去除63,90,130都有余数,三个余数的和是25.这三个余

数中最小的一个是_____.

解：1.设这个自然数为m,且m去除63,90,130所得的余数分别为a,b,c,则

63?a,90?b,130?c都是m的倍数.

于是(63?a)?(90?b)?(130?c)?283?(a?b?c)?283?25?258也是m的倍数.

343. 又因为258?2创则m可能是2或3或6或43 (显然m?1,86,129,258),但是a?b?c?25,故

a,b,c中至少有一个要大于8(否则, a,b,c都不大于8,就推出a+b+c不大于24,

这与a?b?c?25矛盾).根据除数m必须大于余数,可以确定m=43.从而

a=20,b=4,c=1.显然,1是三个余数中最小的.

13. 在1,2,3,??29，30这30个自然数中，最多能取出_____个数,使取出的这些数中,

任意两个不同的数的和都不是7的倍数.

解：15.我们把1到30共30个自然数根据除以7所得余数不同情况分为七组.例如,除以7余1的有1,8,15,22,29这五个数,除以7余2的有2,9,16,23,30五个数,除以7余3的有3,10,17,24四个数,?要使取出的数中任意两个不同的数的和都不是7的倍数，那么能被7整除的数只能取1个，取了除以7余1的数，就不能再取除以7余6的数；取了除以7余2的数，就不能再取除以7余5的数；取了除以7余3的数，就不能再取除以7余4的数.为了使取出的个数最多,我们把除以7分别余1、余2、余3的数全部取出来连同1个能被7整除的数，共有

5+5+4+1=15（个）

所以，最多能取出15个数.

14. 用1?9九个数字组成三个三位数,使其中最大的三位数被3除余2,并且还尽可能地小；次大的三位数被3除余1；最小的三位数能被3整除.那么,最大的三位数是_____.

解：347.

根据使组成的符合条件的三位数,其最大三位数尽可能小的条件,可知它们百位

8，9. 上的数字应分别选用3,2,1；个位上的数字应分别选用7，又根据最小的三位数是3的倍数,考虑在19中应填5,得159.则在37,28中被

3除余2,余1,选用4,6分别填入圆圈中得347,268均符合条件.

这样,最大三位数是347,次大三位数是268,最小三位数是159.

15．桌面上原有硬纸片5张。从中取出若干张来，并将每张都任意剪成7张较小的纸

片，然后放回桌面，像这样，取出，剪小，放回；再取出，剪小，放回；??是否可能在某次放回后，桌上的纸片数刚好是1991？

解： 11. 每次放回后,桌面上的纸片数都增加6的倍数,总数一定是6的倍数加5.而1991?6′331?5,所以是可能的.

16．某班有41名同学，每人手中有10元到50元钱各不相同.他们到书店买书,已知简装书3元一本,精装书4元一本,要求每人都要把自己手中的钱全部用完,并且尽可能多买几本书,那么最后全班一共买了多少本精装书?

解：每人都要把手中的钱用完,而且尽可能多买几本书,意即3元一本的简装书要尽量多买, 4元一本的精装书要尽量少买甚至不买.

我们分三种情况进行讨论:

(1)当钱数被3整除时,精装书就可以不买；

(2)当钱数被3除余1时, 3k?1?3(k?1)?4,精装书只要买1本,其中k为大于2的自然数.

(3)当钱数被3除余2时, 3k?1?3(k?2)?8,精装书只要买2本,其中k为大于2的自然数.

在10至50这41个自然数中,被3除余1和2的数均各有14个.所以全班一共买精装书

14?142?42 (本)

17. 某校开运动会,打算发给1991位学生每人一瓶汽水,由于商店规定每7个空瓶可换一瓶汽水,所以不必买1991瓶汽水,但是最少要买多少瓶汽水?

解：因为73?343?1991?2401?74,不考虑余数,能用空瓶换三次汽水,由于每7个空瓶可换一瓶汽水,原有空瓶不一定能被7整除,那么第二次以后换时要考虑上一次的余数,最多能用空瓶换四次汽水.

111?3)?1707.2825 1991?(1?2777如果买1707瓶汽水, 1707?7?243?6可换243瓶汽水, ?243?6??7?35?4可换35瓶汽水, ?35?4??7?5?4可换5瓶汽水, ?5?4??7?1?2可换一瓶汽水,

1?2?7不能再换. 1707?243?35?5?1?1991.如果买1706瓶,用空瓶换的数量不变,但1706?243?35?5?1?1990.所以最少要买1707瓶汽水.