这是很经典的剩余定理,也叫韩信点兵。
先用通式表示:数M被x除余a,被y除余b;被z除余c,求M的值?
题目的解题思路是:
先求其中两个除数x,y的最小公倍数,用这个最小公倍数P除以第三个除数z,如果余数和第三个余数c相等,则不需要处理,确定好这个最小公倍数;
如果余数和第三个余数c不等,那么就把得到的最小公倍数P乘以一个自然数k1变成最小公倍数的整数倍,使得得数除以第三个除数z得到的余数与c相等,确定好最小公倍数的整数倍。
这样做的目的是,最小公倍数或其整数倍保证了可以整除前面两个数x,y;并且除以第三个除数的余数余M除以第三个除数的余数相等,都是c
同理,可以得到剩余的两组最小公倍数或其整数倍。
再把这三个数相加,得到的数及其整数倍就是分别除以这三个数得到对应的余数。而如果要求的是符合题意的最小的数,则只需把得到的数减去这三个数的最小公倍数的整数倍,所得的得数就是符合题意的最小整数。因为这三个加数中的每个数都是其他两个数的倍数,并且除以第三个除数得到的余数也与第三个余数相等,所以他们的和也符合这个特点。
现在我们用这个题目的具体数字分析:
这个题目可以转变成:
数A被5除余数是3,被6除余数是4;被7除余数是1,求数A的最小值?
由于5,6,7互质
5和6的最小公倍数是30,用30除以7看余数是否与第三个余数1相等,30除以7,余数是2,要使得余数是1,只有把30乘以整数倍,30乘以4倍,得到的数除以7所得余数是2*4-7=1,
确定了第一个数是30*4=120
因为120即保证了是5和6的倍数,又保证了除以7余数是1
同理,找第二个数,5和7的最小公倍数是35, 35除以6的余数是5 ,和余数4不相等,把35变成其倍数,35乘以2倍,得到的数除以6所得的余数是5*2-6=4,
确定了第二个数是35*2=70
找第三个数,6和7的最小公倍数是42,42除以5的余数是2,与第一个余数3不相等,把42变成其倍数,42乘以4倍,得到的数除以5所得的余数是2*4-5=3,
确定了第三个数是42*4=168
把这三个数相加:120 + 70 + 168 = 358
我们来检验:对于除数5来说,120和70都是5的倍数(可表示为5k1,5k2),168除以5所得的余数是3,所以这三个数相加得到的358(5k1+5k2+168)一定也是符合除以5的余数是3
同理,可知358也符合分别除以6和7得到相应的余数。
不只是358符合题意,358减去或加上5 ,6 ,7的最小公倍数210或210的整数倍所得的数也是符合的,比如10除以3余数是1,那么10减去3的整数倍后得到的数,再除以3所得的余数也一定是1,比如(10-3*2)=4除以3余数就是1,原因很简单,自己思考。就是(10土3*n)/3=10/3土n,n是整数部分,没有余数,所以最后余数还是10/3所得到的。
所以符合题意的数有:358土210*n
358 - 210 = 148 ,358 + 210*n
题目要求A的最小整数值,则答案就是148
148
你可以这样想:
被5除余3的,分别是8、13、18、23、28……
其中把它们用6除,余数分别为2、1、0、5、4、3……
即为6个一循环,每循环一次增加30,这样,先找出最小的,满足前两条件的数28,每次加30,分别求出被7除的余数,可以得出148为最小值.
一个数除以5余3除以6余4说明这个数加2以后可以同时整除5和6,也就是30的倍数,那么这个数就是等差数列28 58 88……,这数列上除7余1的最小的是148
一个数除以5余3除以6余4除以7余1(要是最小的自然数)
到YIIYII这里
YII3
这个最小的自然数是------148