剩余定理

剩余问题

在整数除法里，一个数同时除以几个数，整数商后，均有剩余；已知各除数及其对应的余数，从而要求出适合条件的这个被除数的问题，叫做剩余问题。

解法（基础数法）

基础数的条件：

（1）此数必须符合除数自身的余数条件；

（2）此数必须是其他所有各除数的公倍数。

第一步：求各除数的最小公倍数

[3，5，7]=105

第二步：求各除数的基础数

（1）[3] 105÷3=35；[35]÷3＝11……2

（2）[5] 105 ÷ 5=21 ；21÷5=4……1（当于3）；∵1×3=3；∴21×3=63

（3）[7] 105 ÷ 7=15；15 ÷ 7=2……1（当于2）；∵1×2=2；∴15×2=30

第三步：求各基础数的和

35+63+30＝128

第四步：求基准数（最小的，只有一个）

128-105=23

第五步：求适合条件的数X

X＝23+105K（K是整数）

相关定理：

定理1：几个数相加，如果只有一个加数，不能被数a整除，而其他加数均能被数a整除，那么它们的和，就不能被数a整除。

如：

10能被5整除，15能被5整除，但7不能被5整除，所以（10+15+7）不能被5整除。

 

定理2：二数不能整除，若被除数扩大（或缩小）了几倍，而除数不变，则其余数也同时扩大（或缩小）相同的倍数（余数必小于除数）。      

如：

22÷7＝3……1

（22×4）÷7＝12……1×4（＝4）

（22×9）÷7＝28……1×9-7（＝2）

 

转载于:https://www.cnblogs.com/QuentinYo/archive/2013/04/02/2996410.html

相关资源：中国剩余定理python实现