一个题根从小学讲到高中. 从带余除法到中国剩余定理

一个题根从小学讲到高中

----------由带余除法到中国剩余定理

（一）什么是带余除法？

顾名思义,带余除法就是两个整数相除,除不尽而带有余数. 例如:7÷3=2…1.

这个式子的含义是：7除以3是除不尽的,运算的结果是商2余1. 这个式子带有省略号,不算太清楚,所以一般将其改写为;

7=3×2+1.

一般地,如果被除数是b,除以除数a后商数是q,余数是r,则有;

b?aq?r这个式子

题,就主要讲解并消化这个公式.

???

???,是带余除法的基本公式,也是研究整除问题的题根.我们这个专

千万别不屑一顾:无非是带余除法么？有什么高深莫测的？ 那么我且问你,以下几个问题你真的清楚吗？ 1.余数的基本性质.

问题1.如果除数是5,那么余数有哪几种可能？

【解析】直接举例,5,6,7,8,9除以5,余数分别为0,1,2,3,4; 以下10,11,12,13,14除以5,余数仍为0,1,2,3,4;

可以预见,再往下推理,余数仍然逃不出0,1,2,3,4这5个数的范围. 这就是说,任一整数除以5,其余数只有5种可能.

1

一般地说,任一整数除以正整数n,其余数有且只有0,1,2,…,n-1共n种可能. 特别提醒,余数必须是自然数而且比除数要小. 即 在式子???中,必定有0≤r＜a. 2.同余

问题2.写出100以内除以15余数是5的所有整数. 【解析】根据公式b=15a+5.

依次令a=0,1,2,3,4,5,6得:b=5,20,35,50,65,80,95. 同余的字面含义就是余数相等.

定义1:如果两个整数a,b,除以另一个整数c所得余数相等,就称这两个整数关于除数c同余.

（在一些关于整除研究的书籍里,用符号mod表示同余.例如

20≡35（mod15）,表示20,35这两个整数除以15所得余数相等,它们都是5.）

3.整数按同余分类

问题3.证明:任意3个连续正整数之和一定是3的倍数 【证明】将公式???具体写为:b=3k+r. 这里0≤r＜3,且r为整数,∴r=0,1或2.

于是所有整数按此同余可分为3类,即3k,3k+1和3k+2. 也就是任意3个连续整数,有且仅有3种写法: （1）3k,3k+1,3k+2,其和为9k+3; （2）3k-1,3k,3k+1,其和为9k; （3）3k-2,3k-1,3k,其和为9k-3. 无论哪种情况,其和均能为3整除,

2

所以, 任意3个连续正整数之和一定是3的倍数

评注:一般地,如果除数为n, ∵0≤r＜n,且r为整数,∴r=0,1,2,…,n-1 那么所有整数可分为n类,即nk,nk+1,nk+2,…,nk+（n-1）. 事实上,整数分为奇数与偶数,也还是依照公式???按同余分类. 此时b=2k+r,且只有r=0与1. 4.整除

问题4.证明999999能被13整除.

【解析】∵999999=999×1001,而1001=13×11×7 即999999=999×13×11×7,等式右边含有因数13, 故999999必能为13整除.

定义2.如果整数b除以整数a没有剩余（即在式???中,余数r=0）,则称整数a能为整数b整除.

定义3.如果整数b能为整数a整除,则称b为a的倍数, a为b的约数（或因数）如果a是质数,则称a为b的质因数.

问题5.写出999的所有因数,并指出哪些是质因数 【解析】999=3×3×3×37.

故999的所有约数为1,3, 3×3=9, 3×3×3=27,37,3×37=111, 9×37=333,999.共计8个.

在999的所有约数中,只有3与37是质因数.

注意1既不是质数,也不是合数.所以以上因数中,1不能称为质因数. 定义4.任一整数必定有1和本身两个约数,称它们为该整数的当然约数. 5.最大公约数与最小公倍数.

3

问题5. 写出36与45的所有公约数与公倍数 【解析】36的所有约数是1,2,3,4,6,9,12,18,36, 45的所有约数是1,3,5,9,15,45.

其中1,3,9既是36的约数.又是45的约数.所以1,3,9都是36与45的公约数.其中9是它们公约数中最大的,故称9为36与45的最大公约数.

36的倍数依次为36,72,108,144,180,… 45的倍数依次为45,90,135,180,….

其中180既是36的倍数,又是45的倍数,故称为36与45的公倍数. 这两个数的公倍数还有360,540,720,1440,…等无穷多个.但其中180是最小的,所以称180是36与45的最小公倍数.

定义5.几个整数的公约数中最大的一个,称为最大公约数; 几个整数公倍数中最小的一个叫做最小公倍数. 6.互质整数

问题6.25与16有公约数吗?为什么?

24?25?5,16?2【解析】∴25与16除1以外,再无其他公约数.

定义6.两个整数的公约数除1以外,再无其他,则称这两个整数互质. 反之,如果整数a与b互质,那么它们的最大公约数是1,而最小公倍数为a?b. 特别注意:整数的互质是没有传递性的.例如4与5互质,5与6也互质,由此并不能推出4与6也互质.事实上,4与6存在不是1的公约数2,所以它们不互质.

以上我们对公式

???进行了

6个方面的分析.其中最需要掌握,也是最难的重

点知识就是?同余?,这得从孙子问题说起.

（二）从?孙子问题?到 孙子定理

4

1.什么是?孙子问题?？

?孙子问题?源于我国古代流传下来的《孙子算经》,它是世界级的名题.原文是:?今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何？? ①

注意到3,5,7都是质数. ?孙子问题?的实质是：求一个整数N,使它同时满足除以3余2,除以5余3,除以7余2.

假如只需求出这个?孙子问题?的一个答案,倒也简单:

既是这些物品数以3与7除之都余2,那么它最少有3×7+2=23（件） 注意到23正好满足除以5余3,所以所求物品的数量,最少有23件. 可是,23不是本题的唯一解,如果再加上3,5,7的公倍数105的任意整数倍, 即得到这个孙子问题的通解是

N=105k+23 （※）

其中k为非负整数,当k=0,1,2,3…时依次得23, 128,233.338,…等,它们都是这个孙子问题的解.

各位请看:这个公式（1）是不是我们前面提到的带余除法的基本公式？ 我国古人将孙子问题的解法浓缩为如下四句话;

三人同行七十稀，五树梅花廿一枝。 七子团圆正半月，除百零五便得知。

‘三人同行七十稀’,说的是70能够被5与7整除,但是被3除余1;‘五树梅花廿一支’,是说21是3与7的倍数,但被5除余1;‘七子团圆正半月’,是指15能够被3与5除尽,但被7除余1.这3句隐藏着孙子问题的正规解法是：

将70二倍得140,这时它还是5与7的倍数,但符合被3除余2;

5

但无论哪一种分解方法,都很难做到简单明了. 可是你若懂得杨辉三角是怎么回事,解题效果 就会大不一样.

杨辉三角是二项定理的具体模式,它 反映了?a?b?n展开式的系数规律.其基

本形式如右图所示:.例如n=5时,

?a?b??a5?5a4b?10a3b2?10a2b3?5ab4?b5

5a?b?a?b?b?b????【证明】 ??5555543223???a?b??5?a?b?b?10?a?b?b?10?a?b?b?5?a?b?b4?b5??b5 ????a?b??5?a?b?b?10?a?b?b?10?a?b?b3?5?a?b?b4

25432已知a?b能被5整除,故以上各项都能够为25整除. 这就证明了,

a5?b5必能被25整除.

评注:无论使用杨辉三角的哪一行,最终都归结到只需考察该行的最后一项. 虽然解题中使用了?杨辉三角?,但解题思路仍然逃不出余数定理的范围.例如我们考查6除以25的余数是几?,利用?杨辉三角?的解题思路是:

565??5?1??55?5?54?10?53?10?52?5?5?1

可见这个展开式除最后一项是1外,其余各项都含有因数25.

54325?5?5?10?5?10?5?5?5?25M则 记

565?25M?1

各位请看,这个式子是不是还是余数公式???的基本形式.

16

由此确定:

65除以25的余数是1.

因为我们的目的是求余数,故无需去求M到底是几.但确信:M一定是整数. 4.中学数学知识的拓展,为我们处理大数创造了条件. 【例5】证明和数222555?333444是7的倍数.

【分析】解本题需要懂得两点预备知识. 一是二项定理,二是如下两个因式分解公式: 1.当n为奇数时,以n=5为例:

a5?b5??a?b??a4?a3b?a2b3?ab4?b4?2.当n为偶数时,以n=4为例:

?1?

a4?b4??a?b??a3?a2b?ab2?b3?【证明】∵222=7×31+5,

?222555??7?31?5?555?2?

?7M?5555

（根据二项展开式.这个展开式共有556项,其前面555项都含有因数7,故其和不妨记为7M,其中M是没有必要求出的整数）

444333??7?47?4?同理;

444?7N?4444

（其中N是无需求出且不同于M的整数）. 于是只需证明5555?4444是7的倍数.

根据n为奇数时类似于公式（1）的分解式,有

5555?4444?3125111?256111??3125?256??K?3381K

（其中K是无需求出且不同于M,N的整数） ∵3381=7×483是7的倍数,故5是7的倍数.

17

555?4444是7的倍数,从而222555?3334445.利用中学数学探求整除的规律性

【例6】证明3个连续整数之积必定是6的倍数

【分析】将全部整数按照以3除之所得余数规律分类.则3个连续整数有且只有如下3种形式;（1）3k,3k+1,3k+2;（2）3k-1,3k,3k+1;（3）3k-2,3k-1,3k.

以下我们仅以第一种形式给于证明,余两种形式的证法类似,请读者自行完成. 【证明】不妨设此3连续整数为3k,3k+1,3k+2（k为整数）,那么:

3k??3k?1???3k?2??3k?9k2?9k?2?

这个乘积中含有因数3.以下只需证明?9k2?9k?2?含有因数2.

9k2?9k?2?9k?k?1??2对于整数k,只能是奇数或偶数.

?1?

若k为偶数,则（1）式已能为2整除;若k为奇数,则k+1为偶数. （1）式仍能为2整除.

29k?9k?2?必定含有因数2.这就证明了: 3个连续整数这就是说: 式子?之积必定是6的倍数.

评注:例6所揭示的规律还可继续推广.

例如:4个连续整数的积必定能为4×3×2×1=12整除; 5个连续整数的积必定能为5×4×3×2×1=120整除; ……

一般地说,n个连续整数之积必定能为n!?n?n?1??n?2????3?2?1整除. 这里n!表示前n个正整数之积,读作n的阶乘.

小结:本文列举出的所有问题,无论难易,最终都是通过带余除法的公式

18

b?aq?r解决的.这正好反映这个公式是关于整除理论的最原始的知识,所以

是研究有关整除问题时必须紧紧抓住的题根.

在这个公式中,注意a,b,q都是非零整数,而整数r的取值范围必须是0≤r＜a,即r是小于除数的非负整数.

整除问题实质是该公式当r=0时的特殊情况.

中小学数学知识本来是连贯的.可是实际的数学教学却是割裂的.过去小学教师不去研究中学数学,所以难以高瞻远瞩地处理那些有发展前景的数学问题.一些中学教师由于对小学基础数学缺乏研究,也造成了数学教学的脱节.

所以我们主张,题根研究应该从小学开始.不仅孙子问题,还有代数与几何计数问题,面积与体积问题,方程问题等,都可以

一个题根,从小学讲到高中. （六）一组关于剩余定理的练习题 1.写出2016的所有约数

2.写出2016与188的公约数与公倍数

3.一个两位数除2016,余数是1818,求这样的两位数

4.证明:各位数字之和为9的倍数的整数,必定也能够被9整除. 5.由超级计算机运算得到的结果:2还是合数,请说明理由.

6.设a是一个满足下列条件的最大的正整数,使得用a除64所得余数是4, 用a除155所得余数是5, 用a除187所得余数是7,则a属于集合

859433?1是一个质数.问2859433?1是质数

A.?3,4,6?B?7,8,9?C.?10,15,20?D.?25,30,35?

7.一个屋子里有一群人，如果3个人一桌多2个，5个人一桌多4个，7个

19

人一桌多6个，9个人一桌多8个，11个人一桌正好坐满。请问这屋里一共有多少人？

8（选做题）证明:20159（选做题）如果x?2016?20172016?2018能被2016整除.

y?7,证明x7?y7是49的倍数.

55551?2?3???1010（选做题）证明必定能被1?2?3???10整除.

参考答案 1.2016?25?32?7,构造如下多项式的乘法:

?1?7??1?3?32??1?2?22?23?24?25?

故知2016的所有约数共2×3×6=36(个) 请读者根据本展开式,自行写出2016的全部约数.

2.将2016与188分别分解质因数得:2016?7?32?25,188?47?22 所以这两个数的公约数是1,2与4,其中4是最大公约数;

这两个数的公倍数是2016×47=94752;2016×47×2=189504; 2016×47×3=284256;2016×47×4=379008.…,其中94752是它们的最小公倍数

3设此二位数为x,令2016=kx+1818（k为正整数）,则 x=198/k

∵198=2×3×3×11,且x为两位数,

∴取k=2,得x=99;取k=3,得x=66;取k=6,得x=33;取k=9,得x=22取k=18,得x=11.

故所求两位数为99，66，33，22或11. 4,.以四位整数为例给于证明.

设有四位数abcd,其中a,b,c,d均为个位整数.且满足a?b?c?d?9k20

（k为整数）

?abcd?1000a?100b?10c?d??999a?99b?9c???a?b?c?d?

?999a?9b9?c9?k9式中各项均含有因数9,故abcd,必定能够被9整除.

同理,满足题设条件的任何整数,都能够被9整除.

5.是合数.理由是,3个连续整数必定有一个是3的倍数.在

a?2859433?1,a?1?2859433,a?2?2859433?1中,已知a是质数,

有2的因子不可能为3整除,故a?2必定是3的倍数,故为合数.

a?1只含

?64?am?4?am?60?30?2??155?an?5??an?150?30?5,其最大公约数为a6.设??187?ap?7?ap?180?30?6??7.设这屋子共有x个人.

?30,故选D.

依题意,x+1同时是3,5,7,9的倍数,而3,5,7,9的最小公倍数为315. 故设x=315m-1 （1）

又知x为11的倍数,故令x=11n （2）

315m?17m?1?28m?综合（1）,（2）, 315m?1?11n?n?1111

m,n均为整数,故必m=8,19,30,…,8+11k. 代入（1）:x=2519+3465k （3）

当k=0时 ,x有最小值2519.即这个屋子里最少有2519人 8.证明:利用二项展开式; 20152016??2016?1?2016?2016M?1,其中M是无需求出的整数;

（展开式共2017项,符号法则是奇数项为正,偶数项为负,故第2017项必为1）

2017

2016??2016?1?2016?2016N?1,其中N是无需求出的整数.

21

（展开式也是2017项,符号法则全正,故第2017项仍为1） 故20152016?20172016?2018

??2016M?1???2016N?1??2018?2016?M?N?1?,

所以20152016?20172016?2018必能为2016整除.

9.∵x+y=7,∴x=7-y.

将杨辉三角写到第7行是:1 7 21 35 35 21 7 1. 注意到?7?y?的展开式共8行,其符号法则为奇正偶负.故

7x7?y7??7?y??y7

7?77?7?76y?21?75y2?35?74y3?35?73y4?21?72y5?7?7y6

以上各项都含有因数49,这就证明了: 810∵1?2?3???10?55,

55551?2?3???10∴只需证明能被55整除.

x7?y7是49的倍数.

5555S?1?2?3???10,则 记

2S?2?15?25?35???105?

??15?105???25?95???35?85?????105?15??1?

（※）

55432234a?b?a?ba?ab?ab?ab?b????根据公式

（1）中各项都含有因数11,故2S能被11整除.

55555555又2S?0?10?1?9?2?8???10?0?????????2?

再根据公式（※）,（2）中各项均含有因数10, 故2S又能被10整除. 但是10与11互质,这说明2S必能为110整除.也就是S能被55整除.

22

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