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

将21三倍得63, 这时它还是3与7的倍数,但符合被5除余3; 将15二倍得30, 这时它还是3与5的倍数,但符合被7除余2。

接着将所得3数相加,有140+63+30=233.这个数同时满足被3与7除余2, 被5除余3。

‘除百零五便得知’是说3×5×7=105,将233加上或减去105的倍数,所得23,128,338…等都是符合孙子问题的答案。

2. 孙子问题的现代解法

各位如果对公式（※）的来源还有所疑虑的话,以下我们再用现代的方法给于推证:

设所求物品数为x,

由于x分别以3,7除之都余2,∴x=21m+2 （m为非负整数） （1） 由于x以5除之余3,∴x=5n+3 （n为非负整数） （2） 式子（1）与（2）表示同一个数,∴5n+3=21m+2

21m?1m?1?4m?将n用m的代数式表示:n? 55为保证m,n为正整数,只能取m?5k?1（k为非负整数）

代入（1）即得:x=105k+23 （k为非负整数） （3） 所以（3）,也就是（※）式即为孙子问题的通解. 3.什么是孙子定理？ 将前述孙子问题一般化:

已知m1,m2,m3是两两互质的正整数，求最小正整数N，使它被m1,m2,m3除所得余数分别为r1,r2,r3 。

6

将这个问题再一般化: 已知m1,m2,m3,?mn是两两互质的正整数，求最小正整数N，

使它被m1,m2,m3,?mn除所得余数分别为r1,r2,r3,?rn.

《孙子算经》中已经证明,符合上述条件的最小正整数N一定存在,这个结论及其证明方法就是孙子定理,它被西方称之为?中国剩余定理?.

需要提到的是:我国南宋时期的秦九韶对这个问题给出了更为科学且详尽的解法,他的方法被称为?大衍求一术?, 他的成果比之西方的欧拉同样的成果要早500多年.

孙子类问题频频出现于当今的各类数学竞赛与?小升初?等试题之中.到底孙子定理的解法,思想有多厉害,请看:

（三）方法对头,势如破竹.

为说明问题方便,我们约定.每一个符合公式

b?aq?r???

的式子都叫做一个剩余条件,而参与运算的一切字母a,b,q,r等都是整数. 孙子定理的实质是说,无论给于多少剩余条件,则符合所有这些条件的最小整数一定存在且有办法求出.

当然,我们在实际解决问题时,可以运用更简单明了的现代方法.

【例1】（1986.华罗庚金杯赛初赛,9题）有一个整数,除300,262,205后得到相同的余数,这个整数是几？

【解析】设这个整数为x,分别去除300,262,205后所得余数为r,那么

?300?k1x?r????k1?k2?x?38?2?19?262?k2x?r?????k1?k3?x?95?5?19 ?205?kx?r3?7

最后两个式子的因数中,只有19是相同的,可知这个整数为19.

评注.题设3数为x整除后同余,所以它们两两求差后必定是x的倍数,只需将这些差分解质因数即可.

【例2】（1986.华罗庚金杯赛复赛,5题）有一个数,除以3余数是2,除以4余数是1.那么这个数除以12的余数是几?

【解析1】满足除以3余数是2的数有5,8,11,14,17,… 满足除以4余数是1的数有5,9,13,17,…

其中5,17等既满足除以3余2,又满足除以4余1,而它们除以12的余数都是5,故

满足题设条件的数除以12的余数是5.

【解析2】设这个数为x,依题意有:x=3m+2或x=4n+1（其中m,n为正整数）

命3m?2?4n?1?m?4n?1n?1?n? 33可见,当n=3k+1（k为正整数）时,m=4k+1也是正整数. 此时

x=12k+5

故x除以12的余数是5.

评注:解法1虽然简单,但理论推理较差,说服力不够强. 而解法2则是按照题根的思路去做.道理清晰简明.

【例3】（第7届全国数学大赛小五A卷.11题）789,1080,1468除以自然数A（A＞1）,所得的余数都相等,那么A=

【解析】这3个数分别除以A后同余,故只需两两求出其差后分解质因数 ∵1080-789=291=3×97

8

1468-1080=388=4×97. 故所求整数A=97.

【例4】（第3届全国数学大赛小六B卷.8题）一筐苹果,三三数之余一,四四数之余三,,五五数之不足1,这筐苹果最少有 个

【解析】设这筐苹果共有N个.依题意; N=3m+1=4n+3=5p-1. 由3m?1?4n?3?n?3m?2,显然m?4k4?6符合条件.

此时N=3（4k+6）+1=12k+19. 由12k?19.?5p?1?p?12k?202k?2k?4? 55显然k=5s都符合条件,此时N=12×5s+19=60s+19. 取r=0,则N的最小值为19.

评注.本题的剩余条件是3个.我们的办法是首先处理其中两个,得到合理结果后再继续处理另外一个.这种方法,类似于解方程组中的消元.

【例5】（第4届全国数学大赛初赛小六A卷.10题）有一类数,它加上5能

被9整除,它减去5能被7整除,在这类数中,由小到大排列,则第18个数是

【解析】用x表示这类数,那么

?x?5?9m7n?10?9m?5?7n?5?m??

x?5?7n9?显然n??9k?5时m为整数,此时x=7（9k+5）+5=63k+40.

?40;k?17时,x18?63?17?40??1111.

K=0时,x1即所求第18个数是1111.

根据孙子定理,既然符合所给剩余条件的最小正整数可以求出,那么以后的任

9

意一个也就不在话下.

【例6】（第5届全国数学大赛初赛小六A卷.11题）

有若干名学生搬一堆杂志,若每人搬x捆,则剩下20捆未搬走;若每人搬9捆,则最后一名学生只搬6捆.一共有 名学生.

【解析】设一共有n名学生.依题意:

nx?20?9?n?1??6?x?9?23n,

x,n均为整数,且x＞0,故只能n= 23..此时x=8. 答.一共有23名学生.

【例7】5个数2011,2013,2015,2017,2019的积除以7的余数是几? 【解析】注意到2011=7×287+2.

2013=7×287+4, 2015=7×287+6, 2017=7×288+1, 2019=7×288+3.

故只需考察2×4×6×1×3（=144）除以7的余数.显然,这个余数为4. 评注:将题设的每一个数都用公式???的形式表述.既然前面已经是7的倍数,所以以下只需考察各个余数的乘积被7除余几.

【例8】对于任意两整数a,b,试证明a?b,a?b,ab三者之中至少有一个是3的倍数,.

【证明】设a?3m?r1,b?3n?r2这里r1,r2?0,1,2.于是

10

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库一个题根从小学讲到高中 从带余除法到中国剩余定理(2)在线全文阅读。