我有一套一致意见
x = a1 (mod n)
...
x = ak (mod nk)
我想找到
x，这可以用中国剩余定理和相关算法来解决：https://en.wikipedia.org/wiki/Chinese_remainder_theorem例如：https://rosettacode.org/wiki/Chinese_remainder_theorem
对于此特定示例：
x = 1031 (mod 1473)
x = 1141 (mod 1234)
x = 50 (mod 1827)
我尝试过的所有算法都不起作用，因为模不是成对互质的。
但是，
1024360583是一个有效的解决方案：1024360583 % 1473 == 1031
1024360583 % 1234 == 1141
1024360583 % 1827 == 50
什么算法能找到这样的解决方案？
我还实现了《密码学手册》中的加纳算法：它没有解决那个例子。
最佳答案
如你所说，模不是成对素数。你可以检查每一对（三对代表你的三个模），只有一对GCD（最大公约数）大于1的是1473和1827，GCD为3。然后我们寻找除一个以上给定模的所有素数。（有几种方法可以做到这一点。）我们发现3是唯一一个划分多个模的素数，而这个划分多个模的素数的最大幂是3**1 = 3（为了清楚起见，我使用python和fortran中使用的指数表示法，因为插入符号在计算机中也有其他用途）。
这可能会阻止你的方程组得到任何解。我们可以通过用方程中的GCD替换这些模来检验这一点，看看是否有矛盾。
x = 1031 = 2 (mod 3)
x = 50 = 2 (mod 3)
得到的方程是一致的，所以原始系统可能仍然有解。（如果
3的更高的幂也除以多个模，我们也需要检查这些更高的幂。）对于我们发现的每个素数和每个模，我们找到该素数除以模的最高幂在我们的例子中，我们看到3除1473但不3**2，而3**2除1827但不3**3所以我们的最高功率是3**2 = 9，我们看到这个功率和更低功率的方程是一致的。我们现在用新的方程替换这两个相关的方程，在除以最后一段中素数的最大幂之后，用这些模替换模。这意味着用
1473替换1473 / 3 = 491，用1827替换1827 / 9 = 203。我们还为素数的每一个幂除一个以上的模加入了新的方程。现在我们有四个联立模方程：x = 1031 (mod 491)
x = 1141 (mod 1234)
x = 50 (mod 203)
x = 50 (mod 9) [from your original equation #1, 3]
我们可以减少一些方程的右边，得到
x = 49 (mod 491)
x = 1141 (mod 1234)
x = 50 (mod 203)
x = 5 (mod 9)
该系统的解决方案也将在原始系统中工作。
我相信你可以把它转换成一个算法，然后把它转换成计算机代码如果你有更多的问题要问。