中国剩余定理求解器
一堆东西三个三个数剩 2,五个五个数剩 3,七个七个数剩 2:一共有 23 个,或 128 个,或 233 个,每隔 105 就有一个答案。这就是《孙子算经》里的问题,中国剩余定理也由此得名。输入任意同余方程组 x ≡ a (mod n),方程想要多少个、数想要多大都可以,你会看到答案、用你的数字写出的解题过程,以及说明它为什么成立的图示。当方程不能同时成立时,求解器会指出互相矛盾的两个方程,并说明原因。 输入同余方程 x ≡ a (mod n),每行一个:a 是余数,n 是模。用“添加方程”或在最后一个模里按 Enter 添加一行,用 × 删除一行。可以输入最多 200 位的整数,a 可以是负数。也可以选择一个例题。卡片显示最小解以及它每隔多少重复一次;下面是最初几个正解和对每个方程的验算。图示标出满足每个方程的数,每一行都有标记的那一列就是解;余数表同时显示两个方程。解题过程用你的数字写出,可以选教科书构造法或代入法。
它是如何运作的
- 输入方程 x ≡ a (mod n),每行一个,或者选择一个例题,比如孙子问题、一篮鸡蛋或儒略周期。
- 读出最小解、它重复的模,以及最初几个正解,每个解都对所有方程做了验算。
- 用构造法或代入法一步一步跟着解题过程走,并在数轴和余数表之间切换图示。
构造法是怎样做的
当任意两个模都没有公因数时,可以直接构造出解。先把各模相乘:孙子问题中 N = 3 × 5 × 7 = 105。对每个方程取 Nᵢ = N / nᵢ,它是其他每个模的倍数:35、21 和 15。再用扩展欧几里得算法求 Nᵢ 模 nᵢ 的逆元 yᵢ:35 除以 3 余 2,而 2 × 2 = 4 ≡ 1 (mod 3),所以 y₁ = 2;21 和 15 都余 1,所以它们的逆元是 1。于是 x = 2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1 = 233,233 mod 105 = 23。每一项都满足自己的方程,又是其他模的倍数,所以它们的和满足所有方程。
当各模有公因数时
各模有公因数的方程组也可能有解。两个方程 x ≡ a (mod m) 和 x ≡ b (mod n) 能同时成立,当且仅当 a − b 是 gcd(m, n) 的倍数,这时解每隔 lcm(m, n) 重复一次,而不是每隔 m × n。两路分别在第 5 和第 11 分钟发车、每 12 和每 18 分钟一班的公交车,会在第 29 分钟相遇,之后每 36 分钟相遇一次,因为 11 − 5 = 6 是 gcd(12, 18) = 6 的倍数。但 x ≡ 1 (mod 4) 和 x ≡ 4 (mod 6) 永远不能同时成立:第一个让 x 为奇数,第二个让 x 为偶数。整个方程组有解,当且仅当其中每两个方程都有解,求解器正是这样找出互相矛盾的两个方程的。
常见问题
中国剩余定理说的是什么?
如果模 n₁、n₂、… 中任意两个都没有公因数,那么对任意余数 a₁、a₂、…,在 0 到 N − 1 之间恰有一个 x 使每个 i 都满足 x ≡ aᵢ (mod nᵢ),其中 N 是各模的乘积。其他任何解与它相差 N 的倍数:孙子问题的解是 23、128、233 等等,每隔 105 一个。
为什么叫“中国”剩余定理?
已知最早的这类问题出自《孙子算经》,这是一部成书于 3 至 5 世纪之间的中国算书:一些东西三个、五个、七个地数,分别余 2、3、2。秦九韶在 1247 年给出了解这类问题的一般方法,卡尔·弗里德里希·高斯在 1801 年用现代形式表述了这个定理。
如果各模不互素怎么办?
那就可能无解;即使有解,也是每隔各模的最小公倍数重复一次,而不是每隔它们的乘积。两个方程相容,当且仅当它们的余数模两模的 gcd 相同。鸡蛋谜题用的是 2、3、4、5、6 和 7,它们有公因数,但仍然有解:301,每隔 420 重复一次。
RSA 是怎样用中国剩余定理的?
解密 RSA 消息就是计算 c^d mod n,其中 n = p × q。更快的做法是分别计算 c^d mod p 和 c^d mod q,指数分别对 p − 1 和 q − 1 取模,再用定理把两个结果合起来。数的长度减半后,两次幂运算各只需约八分之一的工作量,所以解密快了大约四倍,大多数 RSA 软件都是这样做的。
数可以有多大?
最多 20 个方程,每个数最多 200 位。求解器在你的浏览器中用精确整数计算,所以不论答案多长都是精确的,而且不会发送任何数据。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器