同余方程的解x≡3(mod7),x≡6(mod23),x≡12(mod31)怎么解?

Question

同余方程的解
x≡3(mod7),x≡6(mod23),x≡12(mod31)怎么解?

Answer 1

在古代中国的时候孙子就给出了这类题目的做法：“三人同行七十稀,五树梅花廿一枝,七子团圆月正半,除百零五便得知.”
这道题目用的方法其实一样：
除数7,23,31,最小公倍数就是7×23×31=4991,除7的余数是3,这样乘率就是6,；除以23的余数是6,这样乘率就是7,除以31的余数是12,这样乘率就是26.
把总和算出来：23×31×3×6+7×31×6×7+7×23×12×26=72180.,这是一个符合条件的数,72180-4991×14=2306是最小的数,x的所有解是：2306+4991k（k∈Z）