一堆鸡蛋,3个3个数剩2个,5个5个数剩1个,7个7个数剩3个,请问这堆鸡蛋最少几个?请给出通解
1个回答
个数为x,按3个分组剩2,按5个分组剩1,按7个分组剩3.
方法一：
利用不定方程,结合同余求
设x=3a+2=5b+1=7c+3
(将等式对3取余,x==-1==-b+1==c mod 3)
从而b=2+3*b1,c=-1+3*c1
(从而x==5(2+3b1)+1==7(-1+3c1)+3)
x==11+15b1==-4+21c1
(对5取余,得x==1==-4+c1 mod 5,)
c1=5k
于是x==-4+21*5k==-4+105k==101 mod 105
注意：其中加括号的整行内容可以心算完成.
其实利用以上思路,与中国剩余定理并无矛盾.中国剩余定理的原理相当于拉格朗日插值法；也可以利用类似牛顿插值的方法求解同余式.以上方法类似于后者.而他们,全部可以统一和简化.
方法二：
中国剩余定理：
写成同余记号：
x==2,1,3 mod 3,5,7
取x=2*(5*7a)+1*(3*7b)+3*(3*5c)mod 3,5,7 (@@@)
其中5*7a==1 mod 3；也可以由以上设定(@@@),两边对3取余,推知5*7a==1 mod 3.中国剩余定理就是已知这种解法,预先设定好了.
于是可取5*7a==70.这便是"三人行路七十稀"之口诀的由来,意义就是说取5,7的倍数使之除以3余一,这个倍数正好取70.
看明白了我写的内容,中国剩余定理就明白了.
结果：
x=2*70+21+3*15 mod 3*5*7
==101
相关问题
