中国剩余定理的解法简单易懂
发布网友
发布时间：2023-11-01 15:17
共1个回答
热心网友
时间：2024-08-05 10:56
中国剩余定理5种解法：枚举法，解不定方程法，逐级满足法，化为相同除数的同余式法、才用到典经的、不同除数的同余式组解法。
1、余数定理（Polynomial remainder theorem）是指一个多项式f(x) 除以一个线性多项式(x-a)的余数是 f(a)。若f(a)=0，则(x-a)为多项式f(x)的因式。例如，(5x3+4x2-12x+1)/(x-3) 的余式是 5·33+4·32-12·3+1=136。
2、多项式f(x)除以(x-a)所得的余数等于f(a)。
3、证明：根据除法的定义及性质可知，被除数=除数×商+余数。
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。
解答方法：三人同行七十希，五树梅花廿一枝，七子团圆正半月，除百零五便得知。
意思是:将除以3得余数乘以70，将除以5得余数乘以21，将除以7得余数乘以15，全部加起来后再减去105或105的整倍数，得到的数就是答案。
70X2+21x3+15x2=233=105x2+23。
结果就是23。
解法举例：
例一：一个数，除以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的倍数。
