适用于“孙子问题”的剩余定理_奥数数论问题_奥数知识点-查字典奥数网
 
请输入您要查询的关键词

适用于“孙子问题”的剩余定理

2010-06-29 15:30:50     标签:中国剩余定理

一个数除以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就是合乎条件的最小数.

以上三个步骤适合于解类似"孙子问题"的所有问题.

查看全部
推荐文章
猜你喜欢
附近的人在看
推荐阅读
拓展阅读
相关文章
热门文章
最新文章
猜你喜欢