中国剩余定理详解
一个数除以 3 余 2,除以 5 余 3,除以 7 余 2。这个数是多少?把数一个个试下去,过一会儿就会试到 23,但这个问题里藏着一个定理:只要除数之间没有公因数,在它们的乘积以内总是恰有一个答案,而且不用试就能求出来。这个定理已有大约 1,500 年的历史,至今仍在历法、计算机运算和保护网络的密码学中发挥作用。
《孙子算经》里的问题
《孙子算经》是一部 3 至 5 世纪的中国算书,书中问到一些东西,三个三个数剩 2,五个五个数剩 3,七个七个数剩 2。它的答案是 23,方法至今仍在教:三三数之剩一个就取 70,五五数之剩一个就取 21,七七数之剩一个就取 15,加起来后尽量多地减去 105。2 × 70 + 3 × 21 + 2 × 15 = 233,233 − 2 × 105 = 23。明代的一首口诀把 70、21、15 和 105 这几个数传诵了几百年。秦九韶在 1247 年给出了一般方法“大衍求一术”,同样的问题也出现在斐波那契 1202 年的《计算之书》中,高斯则在 1801 年的《算术研究》中用现代形式表述了这个定理。
定理说的是什么
取模 n₁、n₂、…、nₖ,其中任意两个都没有公因数,再取任意余数 a₁、a₂、…、aₖ。那么在 0 到 N − 1 之间恰有一个整数 x,对每个 i,它除以 nᵢ 都余 aᵢ,其中 N = n₁ × n₂ × … × nₖ。其他所有解都与它相差 N 的倍数。用模运算的记号来说:方程组 x ≡ aᵢ (mod nᵢ) 有解,并且在模 N 意义下唯一。换一种说法,0 到 N − 1 之间的一个数和它的余数列表所含的信息完全相同:3 × 5 × 7 = 105 个数,对应 3 × 5 × 7 = 105 种可能的余数列表,每种恰好用一次。
构造解
70、21 和 15 这几个数并不神秘。每个数除以自己的模余 1,除以其他模余 0:70 = 2 × 35 是 5 和 7 的倍数,除以 3 余 1。一般地,取 Nᵢ = N / nᵢ,它是除 nᵢ 外每个模的倍数,再乘以 yᵢ,即 Nᵢ 模 nᵢ 的逆元。因为 Nᵢ 和 nᵢ 没有公因数,所以逆元存在,扩展欧几里得算法可以求出它:先做求最大公约数的辗转相除,再倒推回裴蜀等式 1 = s × nᵢ + t × Nᵢ,t 就是逆元。于是 x = a₁N₁y₁ + a₂N₂y₂ + … 对 N 取模后满足每个方程,因为每一项都满足自己的方程,而在其他方程中都消失了。
一个方程一个方程地解
还有第二种方法,不需要所有模的乘积。x ≡ 2 (mod 3) 的每个解都形如 x = 2 + 3t。代入下一个方程:2 + 3t ≡ 3 (mod 5),即 3t ≡ 1 (mod 5),两边乘以 3 模 5 的逆元 2,得到 t ≡ 2 (mod 5)。于是 x = 2 + 3 × 2 = 8,前两个方程合起来就是 x ≡ 8 (mod 15)。对第三个方程重复一遍:8 + 15t ≡ 2 (mod 7) 得 t ≡ 1,所以 x ≡ 23 (mod 105)。这种代入法让数保持较小,是计算机通常求解这类方程组的方式,而且在各模有公因数时同样适用。
有公因数的模
如果两个模有公因数,它们的方程就会重叠:x ≡ 1 (mod 4) 已经说明 x 是奇数,而 x ≡ 4 (mod 6) 说明 x 是偶数,所以没有 x 能同时满足两者。一般地,x ≡ a (mod m) 和 x ≡ b (mod n) 能同时成立,当且仅当 a 和 b 除以 g = gcd(m, n) 余数相同,也就是 g 整除 a − b。这时解在模 lcm(m, n) = m × n / g 意义下唯一,而不是模 m × n。古老的鸡蛋谜题里,鸡蛋 2 个、3 个、4 个、5 个或 6 个一拿都剩 1 个,7 个一拿一个不剩,答案是 301,每隔 420 = lcm(2, 3, 4, 5, 6, 7) 重复一次。方程组有解,当且仅当其中每两个方程都相容,所以无解的方程组里总有一对互相矛盾的方程。
历法、计算机与 RSA
1583 年,约瑟夫·斯卡利杰把三个历法循环,即 28 年的太阳周、19 年的太阴周和 15 年的小纪,合成了长 28 × 19 × 15 = 7,980 年的儒略周期。根据定理,每一年都有自己独有的三个周期序号组合,而这个周期从公元前 4713 年开始,那是三个序号最近一次同时为 1 的年份;天文学家至今仍从那里开始数儒略日。计算机用这个定理把巨大的数表示成一组较小的余数来计算,这些余数可以分别、并行地相加和相乘,最后再合起来。RSA 解密也是这样:n = p × q 时,c^d mod n 被拆成模 p 和模 q 的两次幂运算,再用定理合起来,比直接做一次模 n 的幂运算快约四倍。秘密共享方案,例如 Mignotte 方案和 Asmuth–Bloom 方案,把秘密藏在余数里,只有凑够足够多的余数才能还原出秘密。
动手试一试
打开求解器,输入任意同余方程组,最多 20 个方程、每个数最多 200 位,或者选择一个例题:孙子问题、一篮鸡蛋、儒略周期、两路公交时刻表、RSA 解密,以及一个无解的方程组。解题过程用你的数字写出,可以选构造法或代入法,每个逆元都用扩展欧几里得算法求出。图示标出满足每个方程的数,让你看到所有方程交汇的那一列;也可以把两个方程的余数排成一张表,每个数都有自己的格子。
常见问题
同余方程组的解是唯一的吗?
只在相差模的倍数的意义下唯一。如果 x = 23 是孙子问题的解,那么 23 + 105 = 128、233 和 −82 也是,因为加上 105 不改变任何余数。定理说的是在 0 到 104 之间恰有一个解;如果各模有公因数,则在它们的最小公倍数以内恰有一个解。
为什么各模必须两两互素?
对构造法来说,是因为 Nᵢ 必须有模 nᵢ 的逆元,而只有它们没有公因数时逆元才存在。对定理本身来说,是因为公因数会让某些方程重叠:这时方程组要么无解,要么不同的解更少,而且解每隔最小公倍数重复一次,而不是每隔乘积。
怎样手算模逆元?
用扩展欧几里得算法。求 15 模 7 的逆元:15 = 2 × 7 + 1,所以 1 = 15 − 2 × 7,15 × 1 ≡ 1 (mod 7):逆元是 1。求 35 模 3 的逆元:35 = 11 × 3 + 2,3 = 1 × 2 + 1,所以 1 = 3 − 2 = 3 − (35 − 11 × 3) = 12 × 3 − 35,35 模 3 的逆元是 −1 ≡ 2。模很小时,也可以直接试 1、2、3、…,直到乘积余 1 为止。
这个定理和时钟有什么关系?
模 n 的余数就是 n 小时时钟上的一个位置。两个分别有 3 小时和 5 小时的时钟一起出发、每次各走一小时,在回到起点之前会把 15 种位置组合各显示一次,因为 3 和 5 没有公因数。4 小时和 6 小时的时钟走 12 步就回到起点,只显示 24 种组合中的 12 种:一个奇数位置和一个偶数位置永远不会同时出现。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
打开中国剩余定理求解器