具有非成对互质模的同余系统
System of congruences with non-pairwise coprime moduli
我有一套同余式
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 / 3 = 491 替换 1473，用 1827 / 9 = 203 替换 1827。我们还添加了我们为除以多个模数的素数的每个幂得到的新方程。所以现在我们有四个联立模方程：
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)
该系统的解决方案也适用于您的原始系统。
我相信您可以将其转化为算法，然后将其转化为计算机代码。有问题再问。
我有一套同余式
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 / 3 = 491 替换 1473，用 1827 / 9 = 203 替换 1827。我们还添加了我们为除以多个模数的素数的每个幂得到的新方程。所以现在我们有四个联立模方程：
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)
该系统的解决方案也适用于您的原始系统。
我相信您可以将其转化为算法，然后将其转化为计算机代码。有问题再问。