扩展中国剩余定理学习笔记

为什么要扩展中国剩余定理?

建议学习前置芝士:中国剩余定理(不学也不要紧,因为并没有啥关系)

我们知道,中国剩余定理是用来解线性同余方程组的算法,类似下面这个:
$x \equiv a_0 (p_0)$
$x \equiv a_1 (p_1)$
$x \equiv a_2 (p_2)$

很不幸,这里要求$p_0,p_1,p_2$两两互质

.

如果不互质怎么办?当然是把出题者拖出去吊起来打啊。这时候就得有请我们的扩展中国剩余定理了。


什么是扩展中国剩余定理?

如上说述,就是用来求线性同余方程组的定理,但不要求p两两互质。


怎么扩展中国剩余定理?

中国剩余定理的基本原则是将原方程组两两合并直至只有一个方程。

那咋合并呢?

假设我们现在有两个同余方程:

$x \equiv a_0 (p_0)$

$x \equiv a_1 (p_1)$

我们可以先写出式子:

$x=p_0*k_0+a_0=p_1*k_1+a_1$

移项得(我们这里的k在R上任意取值,因此不用纠结它的符号):

$p_0*k_0+p_1*k_1=a_1-a_0$

emmmmm,这个式子是不是有一点点眼熟?

没错,我们可以用exgcd来求这个$k_0$。

这里就引出了我们扩展中国剩余定理的有解的要求:$a_1-a_0$必须为$gcd(p_0,p_1)$的倍数

当然,我们右边的$a_1-a_0$不一定等于$gcd(p_0,p_1)$,因此,我们用exgcd算出来的$k_0$必须乘以$\frac{a_1-a_0}{gcd(p_0,p_1)}$

酱紫,我们将$k_0$膜$\frac{p_1}{gcd(p_0,p_1)}$来得到$k_0$的最小正整数解。(原理请参考这篇文章

接下来,我们可以通过这个神奇的公式(我并不懂为啥可以这样推)来把这两个式子整合起来:

$x \equiv p_0*k_0 + a_0 (lcm(p_0,p_1)) $

.

酱紫,我们就可以一步步把这个方程组浓缩成一个式子啦φ(>ω<*)


例题:

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注