|
借地科普，中国剩余定理。
某数 x，除以两两互质的一组数 m1, m2, ..., mn，余数分别为 a1, a2, ..., an，求x。
为了求 x，需要引入一组数 b1, b2, ..., bn，满足以下条件：
① 当 i ≠ j 时，bi ≡ 0 (mod mj)
② 当 i = j 时，bi ≡ 1 (mod mj)
此时 x 可以容易的给出：
③ x ≡ a1b1+ a2b2+ ... + anbn (mod ∏mi)
或者
③ x = a1b1+ a2b2+ ... + anbn + k∏mi，其中 k 可以取任意整数。
那么如何求 bi 呢，请看下面这个例子。
三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。
在这个例子中，a1 = 3，a2 = 5， a3 = 7，b1 = 70，b2 = 21，b3 = 15。由此得知，bi 一定是除了 ai 外其余所有 a 值乘积的倍数。
令 ri = m1m2...m[i-1]m[i+1]...mn，则必有 ri 和 mi 互质，方程 ciri + dimi = 1 一定有整数解。然后令 bi = ciri，则 bi 必定满足上述①②两式。
问题至此，转化为已知互质的 r 和 m，如何求方程 cr + dm = 1的整数解。此时可用欧几里德扩展算法。
欧几里德定理，也叫辗转相除法，可用于计算两个正整数，r 和 m 的最大公约数 gcd(r, m)。此处gcd(r, m) = 1。
欧几里德扩展算法，在计算最大公约数的每一步记录系数，得到由 r 和 m 组合出 gcd(r, m) 的线性组合系数。即在等式 cr + dm = gcd(r, m) 中，不但求出 gcd(r, m)，还求出了 c 和 d。
例如，r = 23，m = 120
23*0 + 120*1 = 120
23*1 + 120*0 = 23
23*(-5) + 120*1 = 5
23*21 + 120*(-4) = 3
23*(-26) + 120*5 = 2
23*47 + 120*(-9) = 1
至此完成，得到 c = 47，d = -9。
此处 bi = ci*ri = 1081，然后逐次求出所有 bi，再根据③式即可求出 x 。
|
