最新要闻

广告

手机

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

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

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

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

家电

扩展中国剩余定理(EXCRT)

来源:博客园

中国剩余定理(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\) 为负数的情况)

关键词: