Question

一个自然数除以7，8，9分别余1，2，3，而所得的3个商的和是570，这个数是多少？

用中国剩余定理方法解题（尽量），谢谢

Answer 1

最简单的算法是同余.
设该数m, 7|m+6, 8|m+6, 9|m+6, 显然具备同余问题特征. m=7*8*9*k-6=504k-6, K为正整数. 因为随k的变化, a有对应值, 我们需要限定k值即m值, 使得m÷7, m÷8, m÷9的三个商的和是570. 估算m的范围, 三商和570, 每个商接近570÷3=190, 选用除数中的中间数8代表被除数m的平均水平, m接近190*8=1600, 因此凑一下, K=3, m=504*3-6=1512-6=1506. 所以, 该自然数为1506.
用中国剩余定理也可以.
设该数m, 我们要找到m=a*8*9+b*9*7+c*7*8中系数a, b, c的值得到m的值. 问题是m≡a*8*9≡a*2 (mod7), 常用做法是2不动, 取不同的a值, 使得2*a得到目标要求余1, 显然做不到. 因此余数1需要从a*2的积来模7获得, 比如a=4, 11, 18……. , 2a模7余1. 同理c也有同样问题.
保留中国剩余定理的结构形式, 等式两边同乘以6, 不改变余数分布, 重新设某数为n, n=6m
n=6m=6*a*8*9+6*b*9*7+6*c*7*8
n≡6*a*8*9≡1 (mod 7), a=3
n≡6*b*9*7≡2 (mod 8), b=1
n≡6*c*7*8≡3 (mod 8), c=1
n=2010
因为有三商和570的限制, 我们要求的数应该接近1600, 而n为2010, 所以调整一下n值, 减去公倍数[7, 8, 9]=504, 不改变余数分布规律, 所以2010-504=1506. 该数为1506.
不乘以6, 单独调整每项a, b, c的系数值也可以. 得出n值后, 还是需要对比1600这个目标作最后调整.

Answer 2

这个数模7余1，模8余2，由中国剩余定理可得这个数模56余50
这个数模56余50，模9余3，由中国剩余定理可得这个数模504余498
所以这个数最小是498，三个商之和为188，这个数为498+504k，因此三个商之和为188+191k=570 得到k=2，因此这个数为1506

Answer 3

中国剩余定理
q mod i = x, q mod j = y, q mod k = z
令 A = j*k*a, A mod i = 1;
B = i*k*b, B mod j = 1;
C = i*j*c, C mod k = 1; (a, b, c取满足等式的最小整数）
得到 circle = A+B+C -1
q(min) = (A*i + B*j + C*k) mod circle

通过这个得到q的最小值，如果发现不对就将q不断加circle验证商的和是否为570

Answer 4

1056