数论问题之:中国剩余定理例题精讲_奥数数论问题_奥数知识点-查字典奥数网
 
请输入您要查询的关键词

数论问题之:中国剩余定理例题精讲

2011-06-14 17:44:53     标签:中国剩余定理

例1: 一个住校生,家里每星期给他36元生活费。该生每天实际只用生活费5元,某天他小姨到学校看他并给了50元钱,他用此钱买了两本喜爱的课外读物花10元,买学习用具花2元,放假回家后说明情况并给家长交回55元。

问:该生带几个星期的生活费?实际在校住几天?一共有多少钱?花去多少钱?

用方法二解:

列式(36×□+50-10-2)÷5=□……55元

{36×(5+55-50+10+2)+50-10-2}÷(5×36)

=(36×22+50-10-2)÷180

=830÷180……110

答; 1,(110-50+10+2)÷36=2, (括号内□内最小数)

2,(110-55)÷5=11, (括号外□内最小数)

3 36×2+50=122,

4,122-55=67。

答:该生带2个星期的生活费,实际住校11天,一共有122元,花去67元。

例2:有一个年级的同学,每9人一排多5人,每7人一排多1人, 每5人一排多2人,问这个年级至少有多少人?

解答:5 和 9 的公倍数依次是 45、90、135、180、225 ……

这些公倍数中,被7除余1的数是 225

9 和 7 的公倍数依次是 63、126、189、252……

这其中,被5除余2的是 252

5 和 7 的公倍数是 35、70、105、140、……

其中被9除余5的数是 140

把以上 225 252 140 三个数相加,求得

225 + 252 + 140 = 617

5 7 9 三个数的最小公倍数是 5*7*9=315

617-315 = 302

因此 302 就是这个年级至少人数。

例3:一条长长的阶梯,

如果每步跨 2 级,那么最后余 1 级;

如果每步跨 3 级,那么最后余 2 级;

如果每步跨 5 级,那么最后余 4 级;

如果每步跨 6 级,那么最后余 5 级;

如果每步跨 6 级,那么最后余 5 级;

只有当每步跨7级时,最后才刚好走完.

问这条台阶最少有 多少 级.

答案:

如果每步跨 2 级,那么最后余 1 级;

可知 是个奇数如果每步跨 3 级,那么最后余 2 级;

可知+1就是3的整数倍如果每步跨 5 级,那么最后余 4 级;

可知尾是4或9.但是是个奇数,所以是9如果每步跨 6 级,那么最后余 5 级;

可知+1就是6的整数倍只有当每步跨7级时,最后才刚好走完.

可知是7的整数倍7*7=49 7*17=119 49+1不是3的倍数,排除了.

119+1是3和6的整数倍,所以台阶有119级。

例4:一个数除以3余2,除以5余3,除以7余2,求适合这个条件的最小数.孙子的解法是:

先从3和5、3和7、5和7的公倍数中相应地找出分别被7、5、3除均余1的较小数15、21、70 ( 注释:此步又称为求"模逆"运算,利用扩展欧几里得法并借助计算机编程可比较快速地求得.当然,对于很小的数,可以直接死算 ).即

15÷7=2……余1,

21÷5=4……余1,

70÷3=23……余1.

再用找到的三个较小数分别乘以所要求的数被7、5、3除所得的余数的积连加,

15×2+21×3+70×2=233. (将233处用i代替,用程序可以求出)

最后用和233除以3、5、7三个除数的最小公倍数.

233÷105=2……余23,

这个余数23就是合乎条件的最小数.。

运用中国剩余定理解题注意事项

如果整数a除以整数b所得余数是1,那么,整数a的2倍、3倍、4倍、……、(b-1)倍除以整数b所得的余数就分别是

1×2=2,

1×3=3,

1×4=4,

…………

1×(b-1)=b-1.

例如,15÷7=2……余1,即

2×15÷7=4……余2,

3×15÷7=6……余3,

4×15÷7=8……余4,

5×15÷7=10……余5,

6×15÷7=12……余6.

还请大家注意一条经验.

从某数a中连续减去若干个b后,求所得的要求小于数b的差数,实际上就是求数a除以数b所得的余数.

例如,从758里连续减去若干个105后,求所得的要求小于105的差数,实际上就是求758除以105所得的余数.即

758÷105=7……余23.

点击显示
上一篇:数论问题之:中国剩余定理练习题及答案
下一篇:数论问题之:什么是中国剩余定理?
推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关文章
热门文章
最新文章
  • 大家都在看
  • 小编推荐
  • 猜你喜欢
  •