中国剩余定理问题的解题技巧
巡山小妖精
616次浏览
2021年01月26日 06:15
最佳经验
本文由作者推荐
阿飞正传经典台词-
【问题】有１个数，除以７余２．除以８余４，除以９余３，这个数至少是多少？
这种问题称为
“
中国剩余定理
”
问题。
我一般用两种方法解决这类问题。
第一种是逐步满足法，方法麻烦一点，但适合所有这类题目。
第二种是最小共倍法，方法简单，但只适合特殊类型的题目。
还有
“
中国剩余定理
”
的方法，但它不完善且解法较为复杂，普及应 用有一定难度，还不
稳定。所以一般不用。
下面分别介绍一下常用的两种方法。
通用的方法：逐步满足法
【问题】一个数，除以< br>5
余
1
，除以
3
余
2
。问这个数最小是多少 ？
把除以
5
余
1
的数从 小到大排列：
1
，
6
，
11
，
16
，21
，
26
，
……
然后从小到大找除以
3
余
2
的，发现最小的是
11.
所以
11
就是所求的数。
先满足一个条件，再满足另一个条件，所以称之为
“
逐步满足法
”
。
好多数学题目都可以用逐步满足的思想解决。
特殊的方法：最小公倍法
情况一
【问题】一个数除以
5
余
1
，除以
3
也余
1
。问这个数最小是多少？（
1
除外）
除以
5
余
1
：说明这个数减去1
后是
5
的倍数。
除以3
余
1
：说明这个数减去
1
后也是
3
的倍数。
所以，这个数减去
1
后是
3和
5
的公倍数。要求最小，所以这个数减去
1
后就是
3
和
5
的最小公倍数。即这个数减去
1
后是
15
，所以这个数 是
15
＋
1=16.
情况二
1
/
2