一个数除以7余2,除以10余3,除以13余7,这个数至少是多少?

Question

一个数除以7余2,除以10余3,除以13余7,这个数至少是多少?

Answer 1

这个是中国历史上著名的韩信点兵问题,也叫孙子问题(物不知数).
固定的解法是这样的：
【解】
先随便求一个能被7和10整除且除以13余7的数.有固定的方法：
70m-13n=7
（计算前要先把式子两边约一下,这时候没有公因子,不用约）
两个系数70和13,70大,就让70除以13,商5余5,于是
可以化简为(5*13+5)m-13n=7,5m-13(n-5m)=7,令k=n-5m,有
5m-13k=7
两个系数5和13,13大,13除以5商2余3,于是
又可以同样化简5m-(5*2+3)k=7,5(m-2k)-3k=7,令i=m-2k,有
5i-3k=7
这时候,有一个系数是5,一个是3,5大,5除以3商1余2.
又可以同样化简（3*1+2）i-3k=7,3(i-k)+2i=7,有 同样令j=i-k,有
3j+2i=7
这时候,有一个系数是3,一个是2,3大,3除以2商1余1.
又可以同样化简（2*1+1）j+2i=7,2(j+i)+j=7,有 同样令h=i+j,有
2h+j=7
这时候,有一个系数是1,遇到系数是1的时候,要留一个1,即2=1*1+1,而不是2=2*1+0.同样令n=j+h,有
n+h=7
这时候,两边系数都是1,就不能化简了,令n=0,有h=7
代回去,算出j=m-h=-7,i=h-j=14,一直求到m m=56
令a=70m=560*7,且a除以13余7.
按照同样的方法,找到：
b=?①*3,且b除以10余4
c=?②*2,且c除以7余2
然后把三个数加起来
a+b+c=?③,显然这个数满足被7除余2,被10除余3,被13除余7,但不一定是最小
7,10,13三个数的最小公倍数（有固定的算法）是7*10*13=920
然后用?③除以920,④余?⑤
⑤就是结果.
PS:以上解法是固定的算法,对于任意大的数字均可以用该算法求解,不需要试探和猜测.其中求最小公倍数也有固定的算法,即用辗转相除法求得最大公约数间接求得.