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

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

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 代码

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 代码

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 代码

/*解单变元模线性方程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 代码

/*解单变元模线性方程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