当前位置:文档之家› 奥数 余数问题 中国剩余定理

奥数 余数问题 中国剩余定理

被除数÷除数=商+余数(余数<除数)
同余定理1 如果a,b除以c的余数相同,那么我们说a,b对于c是同余的。

并且我们说a,b之间的差能被c整除。

(a b c三个数都是自然数)
例1:有一个大于1的数,除45,59,101所得的余数相同,求这个数可能是多少?
习题1:已知三个数127,99和一个小于30的两位数a除以一个一位数b的余数都是3,求a 和b的值.
同余定理2 a和b的积除以c的余数,等于a,b分别除以c的余数的积或者这个余数的积再除以c所得的余数。

(a b c均为自然数)
例2:22003除以7的余数是多少?
习题2:⨯⨯的积,除以4的余数是_____.
例3:今有一类数,除以3余数是2,除以5余数是3,除以7余数是2.试问这个类数最小那个又什么?(中国剩余定理)
分析:此题就是国际上有名的“中国剩余定理”,早在中国古代人们就中国人民就掌握了这种题型的解法。

此题解法很多,在此介绍同余尝试法。

在附录中有此种题型的一般解法。

题目中给出的条件比较多,假如一开始就同时考虑三个条件,由于关系复杂很难一下子看出答案。

所以应该先考虑其中的一个条件,进而考虑其中的两个条件,最后考虑三个条件,以求出最后答案。

一般应该先考虑除数最大的那个条件,即找出除以7余2的数:
2 ,9 ,16 ,23,30,37,43,50,57……
在此,我们必须在上面的数列中找出满足第二个条件的数,即除以5余3的数,显然,
23,23+5×7,23+5×7×2,23+5×7×3,23+5×7×4……以上数列都能满足前面两个要求。

所以,能够满足‘除以7余2,除以5余3’这两个条件的数有
23,58,93,128,163,198,233,268,303,338……
接下去,我们要继续考虑第三个条件,以上数列中满足除以3余数是2的数,显然
23,23+5×7×3,23+5×7×3×2,23+5×7×3×3……
综上,我们发现
23,128,233,338,443……
均能满足‘除以3余数是2,除以5余数是3,除以7余数是2’,其中最小的数是23。

以上的求解过程我们叫同余尝试法,难点在于尝试这个过程会导致计算量比较大,但是这种解题方法适应性强,条件可以无限制增加,方法不变。

习题3:有一类数,除以7余2,除以8余4,除以9余3。

问这类数中最小的是什么?
习题4:有一类自然数,其中每个数与3的和都是5的倍数,与4的差都是7的倍数。

问这个数最小是多少?
例4:有三个吉利数字,888,518,666,用他们同时除以一个相同的自然数,所得的余数为a,a+7,a+10.试问这个自然数是多少?
习题5:140,225,293同时除以某一个自然数得到的余数相同,试问这个自然数是多少?余数又是多少?
例5:如果时针现在表示的时间是18点整,那么分针旋转1990圈之后是_____点钟.
习题6:1999年1月1日是星期五,试问2002年6月1日是星期几?
例6:节日的街上挂起了长长的一排彩灯,共2013盏。

从第一盏开始,按照5盏红灯,4盏黄灯,3盏蓝灯,2盏绿灯不断地排下去。

问:
(1)第1982盏灯的颜色是什么?
(2)蓝灯共有多少盏?
习题7:甲乙丙丁四个小朋友玩报数游戏,规定,甲报1乙报2丙报3丁报4甲报5乙报6丙报7……,问报2012的那个人是谁?、
【基础训练】
1.小东在计算除法时,把除数87写成78,结果得到的商是54,余数是8.正确的商是_____,余数是_____.
2. a÷24=121……b,要使余数最大,被除数应该等于_____.
3. 一个三位数被37除余17,被36除余3,那么这个三位数是_____.
4. 今天周四,2012天之后是星期________
5. ⨯⨯的积,除以5的余数是_____.
6. 如果时针现在表示的时间是18点整,那么分针旋转1990圈之后是_____点钟.
7. 如果按红、橙、黄、绿、青、蓝、紫的顺序,将
……1992只彩灯依次反复排列,那么_____颜色的彩
1991个1992
灯必定要比其他颜色的彩灯少一只.
【难题挑战】
1.393除以一个两位数,余数为8,这样的两位数有_____个,它们是_____. 2.自然数n除63,91,129所得余数之和为25,则n是多少?
3.盒乒乓球,每次8个8个地数,10个10个地数,12个12个地数,最后总是剩下3个.这盒乒乓球至少有多少个?
4.韩信点兵:有兵一队,若列成五行纵队,则末行一人,成六行纵队,则末行五人,成七行纵队,则末行四人,成十一行纵队,则末行十人.求兵数.
5.有一堆棋子,三个三个地数剩下2个,五个五个地数剩下4个,七个七个地数剩下6个.问这堆棋子最少有多少个?
6.某数除以7余3,除以8余4,除以9余5.从小到大求出适合条件的十个数.
7.某数除以5余2,除以7余4,除以11余8.求适合条件的最小数.
8.一猴子数一堆桃子.两个两个地数剩下1个,三个三个地数剩下1个,五个五个地数剩下3个,七个七个地数剩下3个.问这堆桃子最少是多少个?
9.(小学数学奥林匹克初赛)有苹果,桔子各一筐,苹果有240个,桔子有313个,把这两筐水果分给一些小朋友,已知苹果等分到最后余2个不够分,桔子分到最后还余7个桔子不够再分,求最多有多少个小朋友参加分水果
【超越极限】
小明往一个大池里扔石子,第一次扔1个石子,第二次扔2个石子,第三次扔3个石子,第四次扔4个石子……,他准备扔到大池的石子总数被106除,余数是0止,那么小明应扔_____次.
【中国剩余定理】
在中国数学史上,广泛流传着一个“韩信点兵”的故事:
韩信是汉高祖刘邦手下的大将,他英勇善战,智谋超群,为汉朝的建立了卓绝的功劳。

据说韩信的数学水平也非常高超,他在点兵的时候,为了保住军事机密,不让敌人知道自己部队的实力,先令士兵从1至3报数,然后记下最后一个士兵所报之数;再令士兵从1至5报数,也记下最后一个士兵所报之数;最后令士兵从1至7报数,又记下最后一个士兵所报之数;这样,他很快就算出了自己部队士兵的总人数,而敌人则始终无法弄清他的部队究竟有多少名士兵。

这个故事中所说的韩信点兵的计算方法,就是现在被称为“中国剩余定理”的一次同余式解法。

它是中国古代数学家的一项重大创造,在世界数学史上具有重要的地位。

最早提出并记叙这个数学问题的,是南北朝时期的数学著作《孙子算经》中的“物不知数”题目。

这道“物不知数”的题目是这样的:
“今有一些物不知其数量。

如果三个三个地去数它,则最后还剩二个;如果五个五个地去数它,则最后还剩三个;如果七个七个地去数它,则最后也剩二个。

问:这些物一共有多少?”
用简练的数学语言来表述就是:求这样一个数,使它被3除余2,被5除余3,被7除余2。

因为最早出现在《孙子算经》中,这题又称孙子问题。

孙子问题的解法,以现代的说法,是找出三个关键数70,21,15。

解法的意思就是用70乘3除所得的余数,21乘5除所得的余数,15乘7除所得的余数,然後总加起来,除以105的余数就是答案。

即题目的答案为
70×2+21×3+15×2
=140+63+30
=233
233-2×105=23
公式:70a+21b+15c-105n
关键是找出70 21 15
解法中的三个关键数70,21,15,有何妙用,有何性质呢?首先70是3除余1而5与7都除得尽的数,所以70a是3除余a,而5与7都除得尽的数,21是5除余1,而3与7都除得尽的数,所以21b是5除余b,而3与7除得尽的数。

同理,15c 是7除余c,3与5除得尽的数,总加起来70a+21b+15c 是3除余a,5除余b ,7除余c的数,也就是可能答案之一,但可能不是最小的,这数加减105(105=3*5*7)仍有这样性质,可以多次减去105而得到最小的正数解。

《孙子算经》给出了这道题目的解法和答案,用算式表示即为:
你能看明白吗?。

相关主题