扩展中国剩余定理(EXCRT)

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

扩展中国剩余定理(EXCRT)

2023-06-15 18:07:24 来源：博客园

中国剩余定理(CRT)不能解决模数不互质情况的模线性同余方程组。这是中国剩余定理的原理所决定的。

但当我们的模数不互质时，这个方式显然就寄掉了，因此我们要打破原有的思路，去找一个新的方式解不定方程组，这时我们的扩展中国剩余定理（EXCRT）就出现了

假设我们现在有如下不定方程组

【资料图】

\[\begin{cases} x \equiv r_1(mod \ m_1) \\ x \equiv r_2(mod \ m_2) \\ x \equiv r_3 (mod \ m_3) \\ \cdot \cdot \cdot \cdot \cdot \cdot \cdot\end{cases}\]

显然我们可以得到 $ x = m_1k_1 + r_1 = m_2k_2 + r_2$ ---------- $(1)$

则我们移项可得 $ m_1k_1 + m_2k_2 = r_2 - r_1$ ---------- $(2)$

这里我们 $m_2k_2$ 的系数变为正，是因为 $k_2$ 是任意整数，所以前面的系数不会影响整个式子）

我们已知式子 $m_1p_1 + m_2p_2 = \gcd(m_1,m_2)$ 将 $d$ 设为 $ \gcd(m_1,m_2) $ 。

根据裴蜀定理，此时我们要进行判断，判断 $r_2-r_1$ 是否为 $\gcd(m_1,m_2)$ 的倍数，若是，那么有解，若不是，那么无解。

判断完是否有解后我们可以的到一个显然的式子 $m_1p_1+m_2p_2+km_1m_2-km_1m_2=m_1p_1+m_2p_2=d=\gcd(m_1,m_2)$

此时最左边的式子我们可以化简为 $m_1(p_1+km_2)+m_2(p_2-km_1)=d$

由于我们要找到原式子的通解，所以此时我们将等式两边同乘 $ \dfrac {r_2-r_1}{\gcd(m_1,m_2)} $

则可以得到式子 $m_1(\dfrac {p_1(r_2-r_1)}{\gcd(m_1,m_2)} + \dfrac {km_2(r_2-r_1)}{\gcd(m_1,m_2)}) + m_2(\dfrac {p_2(r_2-r_1)}{\gcd(m_1,m_2)}- \dfrac {km_1(r_2-r_1)}{\gcd(m_1,m_2)}) = r_2-r_1$ ---------- $(3)$

由上面的等式 $(2)$ 得可将 $(3)$ 式右面 $r_2-r_1$ 的式子代换成 $ m_1k_1 + m_2k_2 $

从而得到的等式 $m_1(\dfrac {p_1(r_2-r_1)}{\gcd(m_1,m_2)} + \dfrac {km_2(r_2-r_1)}{\gcd(m_1,m_2)}) + m_2(\dfrac {p_2(r_2-r_1)}{\gcd(m_1,m_2)}- \dfrac {km_1(r_2-r_1)}{\gcd(m_1,m_2)}) = m_1k_1 + m_2k_2 $

由此我们显然可以得到

\[m_1k_1 = m_1(\dfrac {p_1(r_2-r_1)}{\gcd(m_1,m_2)} + \dfrac {km_2(r_2-r_1)}{\gcd(m_1,m_2)})\]\[m_2k_2 = m_2(\dfrac {p_2(r_2-r_1)}{\gcd(m_1,m_2)} - \dfrac {km_1(r_2-r_1)}{\gcd(m_1,m_2)})\]

消掉第一个式子中的 $m_1$ 。则我们求得 $k_1=p_1\dfrac {(r_2-r_1)}{\gcd(m_1,m_2)} + km_2 \dfrac {(r_2-r_1)}{\gcd(m_1,m_2)}$ ---------- $(4)$

由于 $k$ 是任意的整数，因此我们可以将 $k$ 的系数化成 $m_1m_2 \dfrac {1}{\gcd(m_1,m_2)}$、

$k_1=p_1\dfrac {(r_2-r_1)}{\gcd(m_1,m_2)} + km_2 \dfrac {1}{\gcd(m_1,m_2)}$ ---------- $(4)$

此时我们就求得了原式的一个通解 $k_1$ 。因为如果直接将下面的式子带入代码中很可能会溢出，所以我们要先将 $k_1$ 的最小整数解求出。

而求最小正整数解的方法是先将 $km_2 \dfrac {1}{\gcd(m_1,m_2)}$ 用模数 $\dfrac {m_2}{\gcd(m_1,m_2)}$ 先模去，并且同时将 $p_1\dfrac {(r_2-r_1)}{\gcd(m_1,m_2)}$ 也用 $\dfrac {m_2}{\gcd(m_1,m_2)}$ 模去。然后将式子加上模数 $\dfrac {m_2}{\gcd(m_1,m_2)}$ 防止出现负数，最后再模上 $\dfrac {m_2}{\gcd(m_1,m_2)}$ 将 $\dfrac {m_2}{\gcd(m_1,m_2)}$ 不是负数的情况除去。

k1 = k1 * (r2 - r1) / gcd;//求出式子里的前半部分k1= (k1 % (m2 / gcd) + (m2 / gcd)) % (m2 / gcd);//这里的k1要先模式为了防止出现负数的情况

我们将现在得到的等式 $(4)$ 带入等式 $(1)$ 则显然可以得到

\[x = m_1(p_1\dfrac {(r_2-r_1)}{\gcd(m_1,m_2)} + km_2 \dfrac {1}{\gcd(m_1,m_2)}) + r_1\]

从而得到最终的式子

\[x = p_1m_1\dfrac {(r_2-r_1)}{\gcd(m_1,m_2)} + km_1m_2 \dfrac {1}{\gcd(m_1,m_2)} + r_1\]

我们此时显然是知道 $m_1,m_2,r_1,r_2,p_1,\gcd(m_1,m_2)$ 的值，但我们不知道 $k$ 的值，那么这时我们只要模上 $k$ 的系数即可消掉 $k$ 。即把模数变为 $m_1m_2 \dfrac {(r_2-r_1)}{\gcd(m_1,m_2)}$

此时我们就将两个不定方程组合并完成了

$x \equiv p_1m_1\dfrac {(r_2-r_1)}{\gcd(m_1,m_2)} + r_1 (mod \ \dfrac {m_1m_2}{\gcd(m_1,m_2)})$

则此时新的不定方程的 $r$ 为 $\dfrac {(r_2-r_1)}{\gcd(m_1,m_2)} + r_1$ , $m$ 为 $\dfrac {m_1m_2}{\gcd(m_1,m_2)}$

再继续往下合并

最后我们可以合并成唯一一个式子 $x \equiv r(mod \ m)$

则 $x$ 的最小整数解为 $ x = ( r \ mod \ m + m ) \ mod \ m $

（ $r \ mod \ m+m$ 中加 $m$ 是为了防止出现 $r$ 为负数的情况）

关键词：