模数非两两互质的同余方程组求解技术问询

当模数非两两互质时，标准的中国剩余定理（CRT）确实无法直接应用——这正是你遇到的问题核心。不过别担心，这类方程组依然有求解方法，我们可以通过逐步合并同余式的方式来处理。

核心思路：两两合并同余式 #

对于任意两个同余式：

• ( x \equiv a_1 \pmod{n_1} )
• ( x \equiv a_2 \pmod{n_2} )

我们可以将其转化为寻找整数 ( k )，使得 ( a_1 + k \cdot n_1 = a_2 \pmod{n_2} )，也就是：
[ k \cdot n_1 \equiv (a_2 - a_1) \pmod{n_2} ]

这个线性同余方程有解的前提是：( \gcd(n_1, n_2) ) 能整除 ( (a_2 - a_1) )——这也是整个方程组有解的必要条件。如果有解，我们可以求出 ( k ) 的最小正整数解，进而得到合并后的同余式：
[ x \equiv x_0 \pmod{\text{lcm}(n_1, n_2)} ]
其中 ( \text{lcm} ) 是两个模数的最小公倍数。之后重复这个合并步骤，直到处理完所有方程。

针对你的示例方程组求解 #

我们以你给出的三个同余式为例，一步步推导：

1. ( x \equiv 1031 \pmod{1473} )
2. ( x \equiv 1141 \pmod{1234} )
3. ( x \equiv 50 \pmod{1827} )

第一步：合并前两个方程

首先将第一个方程表示为 ( x = 1473m + 1031 )，代入第二个方程：
[ 1473m + 1031 \equiv 1141 \pmod{1234} ]
化简得 ( 239m \equiv 110 \pmod{1234} )（因为 ( 1473 \mod 1234 = 239 )）。

用扩展欧几里得算法求得239的逆元为253（mod 1234），因此：
[ m \equiv 110 \times 253 \equiv 682 \pmod{1234} ]

代入 ( x = 1473m + 1031 )，得到前两个方程的合并解：
[ x \equiv 1005617 \pmod{1817682} ]
（其中 ( 1817682 = 1473 \times 1234 )）

第二步：合并第三个方程

将合并后的解表示为 ( x = 1817682t + 1005617 )，代入第三个方程：
[ 1817682t + 1005617 \equiv 50 \pmod{1827} ]

化简后得到 ( 1644t \equiv -717 \pmod{1827} )，两边除以 ( \gcd(1644, 1827)=3 )，简化为：
[ 548t \equiv 370 \pmod{609} ]

用扩展欧几里得算法求得548的逆元为599（mod 609），因此：
[ t \equiv 370 \times 599 \equiv 563 \pmod{609} ]

代入 ( x = 1817682t + 1005617 )，当 ( t=563 ) 时，得到最小正整数解：
[ x = 1817682 \times 563 + 1005617 = 1024360583 ]
这正是你给出的有效解。

总结步骤 #

处理非两两互质的同余方程组时：

• 依次两两合并同余式，每次合并前先验证相容性（( \gcd(n_i,n_j) ) 需整除 ( |a_i -a_j| )），不相容则方程组无解；
• 若相容，求解线性同余方程得到合并后的同余式（模数为两数的最小公倍数）；
• 重复合并直到所有方程处理完毕，最终解的形式为 ( x \equiv x_0 \pmod{M} )（( M ) 是所有模数的最小公倍数）。

内容的提问来源于stack exchange，提问作者JoseKilo