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