模线性方程组与中国剩余定理

这篇文章会比较杂乱,因为好多内容都被我搞到一块来了…先写一个内容摘要可供参考:

  1. 利用扩展欧几里得算法(exgcd)求解二元一次不定方程
  2. 利用exgcd求解单变元模线性方程
  3. 利用中国剩余定理(CRT)与扩展中国剩余定理(exCRT)求解单变元模线性方程组
    ……

一 求解二元一次不定方程

1 理论

关于$x,y$的,形如$ax+by = c$的方程被称作二元一次不定方程。在实数域中,不定方程有无限组解,因为它可以被看作一条二维平面内的直线,直线上每一个点都对应方程的一组实数解。

但是不定方程却不一定有$x,y$都为整数的解(以下通称“整数解”)。根据扩展欧几里得定理我们知道:不定方程$ax+by=\text{gcd}(a,b)$一定存在整数解。但是推广到一般形式呢?
我们不妨将$ax+by=c$两边同时除以$\text{gcd}(a,b)$,得$a/\text{gcd}(a,b)\times x+b/\text{gcd}(a,b) \times b = c/\text{gcd}(a,b)$。假设$x,y$均为整数,则等式左边的部分$a/\text{gcd}(a,b)\times x+b/\text{gcd}(a,b) \times b$一定是整数,故等式右边的部分$c/\text{gcd}(a,b)$也一定是整数,可知$ax+by=c$存在整数解的条件是$\text{gcd}(a,b)|c$($\text{gcd}(a,b)$是$c$的因子)。

于是我们知道了二元一次不定方程整数解存在性的判定方法,然后我们需要解这个不定方程。

将方程两边同时除以$c/\text{gcd}(a,b)$,化为$\dfrac{a·\text{gcd}(a,b)}{c}\times x+\dfrac{b·\text{gcd}(a,b)}{c}\times y =\text{gcd}(a,b)$。然后我们再建立一方程使得$ax’+by’ = \text{gcd}(a,b)$,使得可以用exgcd求出该方程的特解$x’,y’$。
于是我们获得了$\dfrac{a·\text{gcd}(a,b)}{c}\times x+\dfrac{b·\text{gcd}(a,b)}{c}\times y =ax’+by’$,因为一定存在$x’|x,y’|y$,于是推出$x = x’\times\dfrac{c}{\text{gcd}(a,b)},y = y’\times\dfrac{c}{\text{gcd}(a,b)}$。

然后我们就求出了二元一次不定方程的一组特解,通解:令$kx = b/\text{gcd}(a,b),ky = a/\text{gcd}(a,b)$,则$x+i\times kx,y-i\times ky\text{ }(i\in Z)$是方程的通解。

2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
LL gcd(LL a,LL b){
return b ? gcd(b,a%b):a;
}
//用ExGcd求不定方程 ax+by = c的一组特解(x0,y0)
//通解: x=x0+i*kx,y=y0-i*ky (i = 0,±1, ±2, ...)
void _exgcd(LL a,LL b,LL &x,LL &y){ //普通的exgcd
if(!b){
x = 1; y = 0;
return;
}
_exgcd(b,a%b,x,y);
int t = x; x = y; y = t-(a/b)*y;
}
bool ExGcd(LL a,LL b,LL c,LL &x0,LL &y0,LL &kx,LL &ky){
LL g = gcd(a,b);
if(c % g) return false; //无解
_exgcd(a,b,x0,y0);
LL kc = c/g;
x0 *= kc; y0 *= kc;
kx = b/g; ky = a/g;
return true;
}

二 求解单变元模线性方程

1 理论

关于$x$的,形如$ax+k\equiv b (\text{mod }m)$的方程被称作单变元模线性方程。该方程可以被化为一般形式$ax\equiv b(\text{mod }m)$(注意这里的等式和上面的等式中,$b$并不表示同一个数)。

解方程$ax\equiv b(\text{mod }m)$需要先把它去除同余。不妨把$ax$与$b$相差的那一部分($|ax-b|$)补齐,于是得到等式$ax=b+km$,可化为$ax-mk=b$,实际上是一个关于$x,k$的二元一次不定方程。
然后就可以exgcd求解。注意,我们只关注$x$的取值,而对$k$不作要求。并且$x$应该在模$m$的情况下才有意义,所以我们关注的是$x$的最小非负整数解。

2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
LL gcd(LL a,LL b){
return b ? gcd(b,a%b):a;
}
//用ExGcd求不定方程 ax+by = c的一组特解(x0,y0)
//通解: x=x0+i*kx,y=y0-i*ky (i = 0,±1, ±2, ...)
void _exgcd(LL a,LL b,LL &x,LL &y){
if(!b){
x = 1; y = 0;
return;
}
_exgcd(b,a%b,x,y);
int t = x; x = y; y = t-(a/b)*y;
}
bool ExGcd(LL a,LL b,LL c,LL &x,LL &y,LL &kx,LL &ky){
LL g = gcd(a,b);
if(c % g) return false; //无解

_exgcd(a,b,x,y);
LL kc = c/g;
x *= kc; y *= kc;
kx = b/g; ky = a/g;
return true;
}
//求模线性方程 ax ≡ b(mod m)的最小非负整数解x0
//化成ax-my = b
//通解x = x0+i*k
bool LineModEqu(LL a,LL b,LL m,LL &x0,LL& k){
LL y0,kx,ky;
if(!ExGcd(a,m,b,x0,y0,kx,ky)) return false;
k = kx;
x0 %= k;
x0 = (x0+k)%k; //取非负整数
return true;
}

然后你不觉得这个东西可以来求逆元吗???


三 中国剩余定理

经过了前面的铺垫,终于可以步入正题了。

1 单变元模线性方程组

把$n$个$x$系数为$1$的单变元模线性方程搞到一起,就得到了一个单变元模线性方程组。它是类似于这样的:
$$ \begin{cases} x \equiv b_1(\text{mod }m_1) \newline x \equiv b_2(\text{mod }m_2) \newline x \equiv b_3(\text{mod }m_3) \newline …\newline x \equiv b_n(\text{mod }m_n) \end{cases} $$

2 中国剩余定理

若单变元模线性方程组的模数$m_1,m_2,m_3,…,m_n$两两互质,那么这个同余方程组可以用中国剩余定理(CRT)来求解。否则用扩展中国剩余定理(exCRT)求解,下面讲。

我们设$M = \prod\limits_{i=1}^n m_i,M_i = M/m_i$。对于每一个$M_i$,求出它在模$m_i$意义下的逆元$t_i$,则$x = \sum\limits_{i=1}^n M_i·t_i·b_i$。然后这个$x$是在模$M$情况下有意义,所以将它模$M$就求出了最小非负整数解。

3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/*解单变元模线性方程ax ≡ b*/
LL gcd(LL a,LL b){return b ? gcd(b,a%b) : a;}
void _exgcd(LL a,LL b,LL &x,LL &y){
if(!b){
x = 1; y = 0;
return;
}
_exgcd(b,a%b,x,y);
LL tx = x; x = y; y = tx-(a/b)*y;
}
bool ExGcd(LL a,LL b,LL c,LL &x,LL &y,LL &kx,LL &ky){
LL g = gcd(a,b);
if(c % g) return false;
_exgcd(a,b,x,y);
LL kc = c/g;
x *= kc; y *= kc;
kx = b/g; ky = a/g;
return true;
}
bool LineModEqu(LL a,LL b,LL m,LL &x,LL &k){
LL y,kx,ky;
if(!ExGcd(a,m,b,x,y,kx,ky)) return -1;
k = kx; x %= k; x = (x+k)%k;
return true;
}

/*CRT*/
void CRT(int n,LL &x,LL *b,LL *m){
LL M=1;
for(int i=1;i<=n;i++) M *= m[i];
x = 0;
for(int i=1;i<=n;i++){
LL Mi = M/m[i],Ti,k;
LineModEqu(Mi,1,m[i],Ti,k); //求逆元
(x += b[i]*Mi*Ti) %= M;
}
x = (x+M)%M; //搞成非负数
}

四 扩展中国剩余定理

1 理论

单变元模线性方程组的模数不满足两两互质,就要使用扩展中国剩余定理合并方程。

先考虑$n=2$(仅有两个方程)的情况。类似于这样:
$$ \begin{cases} x \equiv b_1(\text{mod }m_1) \newline x \equiv b_2(\text{mod }m_2) \end{cases} $$ 去掉同余,我们推出$x = k_1m_1+b_1 = k_2m_2+b_2$。然后后面的部分可以变型成$k_1m_1 -k_2m_2 = b_2-b_1$,然后你发现这坨东西又可以exgcd……
于是我们求出了上面那个二元一次不定方程的一组最小非负整数解$k_1,k_2$。设$x’ = k_1m_1+b_1,m’ = \text{lcm}(m_1,m_2)$。

我们假设$k_1m_1+b_1 \equiv k_2m_2+b_2 (\text{mod }k)$成立,则条件是$m_1|k$且$m_2|k$。故可知最小的$k = m’$。故推出$x\equiv x’ (\text{mod }m’)$,也就是把两个方程合并成了一个。

最后只会剩下一个单变元模线性方程,你再exgcd一遍就解出来了。

然后你未免会发现上面的说法存在一些逻辑上的缺漏。没办法,水平有限,没法搞得太严谨,将就着理解,还是背代码更重要。

2 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/*解单变元模线性方程ax ≡ b*/
LL gcd(LL a,LL b){return b ? gcd(b,a%b) : a;}
void _exgcd(LL a,LL b,LL &x,LL &y){
if(!b){
x = 1; y = 0;
return;
}
_exgcd(b,a%b,x,y);
LL tx = x; x = y; y = tx-(a/b)*y;
}
bool ExGcd(LL a,LL b,LL c,LL &x,LL &y,LL &kx,LL &ky){
LL g = gcd(a,b);
if(c % g) return false;
_exgcd(a,b,x,y);
LL kc = c/g;
x *= kc; y *= kc;
kx = b/g; ky = a/g;
return true;
}

/*ExCRT*/
bool ExCRT(int n,LL &x,LL *b,LL *m){
b[0] = 0; m[0] = 1; //x ≡ 0(mod 1)
LL k0,ki,kk0,kki;
for(int i=1;i<=n;i++){ //合并方程
if(!ExGcd(m[0],m[i],b[i]-b[0],k0,ki,kk0,kki)) return false; //解不定方程
k0 %= kk0;
b[0] += k0*m[0]; //x' = b0*k0*m0
m[0] = (m[i]*m[0])/gcd(m[i],m[0]); //m' = lcm(m0,mi)
b[0] %= m[0]; //在取模意义下
b[0] = (b[0]+m[0])%m[0]; //搞成非负数
}
x = b[0]; //x ≡ b0(mod 1) => x = b0
return true;
}

参考资料:初等数论(1) - CDC

$$ - - - - \mathcal{End} - - - - $$


评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×