中国剩余定理学习笔记

概述

中国剩余定理可以求解同余方程组，如对下列方程组：

$$\begin{cases}x\equiv a_1 \ (mod \ m_1) \\ x\equiv a_2 \ (mod \ m_2) \\ x\equiv a_3 \ (mod \ m_3) \\ \ldots \\ x\equiv a_n \ (mod \ m_n) \end{cases}$$

求解最小的 $x$ 。

求解

令：

$$M=m_1\times m_2\times m_3\times \ldots \times m_n$$

那么方程组在 $mod \ M$ 的情况下有且仅有一个整数解。

模数互质

可以直接求解。令 $M_i=M\div m_i$ ，那么

$$x\equiv \sum_{i=1}^n a_i\times M_i\times M_i^{-1} \ (mod \ M)$$

其中 $M_i^{-1}$ 为 $M_i$ 在 $mod \ m_i$ 意义下的逆元。

inline int crt()
{
    int M=1,ans=0;
    for (int i=1;i<=n;i++) M*=A[i];
    for (int i=1;i<=n;i++)
    {
        int Mi=M/A[i],x=0,y=0;
        exgcd(Mi,A[i],x,y);
        ans=(ans+B[i]*Mi*x)%M;
    }
    ans=(ans+M)%M;
    return ans;
}

模数不互质

可以用合并的思想做。

对下面的同余方程组：

$$\begin{cases}x\equiv a_1 \ (mod \ m_1) \\ x\equiv a_2 \ (mod \ m_2) \end{cases} $$

可以化为：

$$\begin{cases} x=k_1\times m_1+a_1 \\ x=k_2\times m_2+a_2\end{cases}\tag{1}$$

也就是说：

$$m_1\times k_1-m_2\times k_2=a_2-a_1$$

显然可以用 $\text{exgcd}$ 求解任意解 $X$ ，那么 $k_1$ 的最小解为：

$$k_1=X\times \dfrac{(a_2-a_1)}{\text{gcd}(m_1,m_2)} \ mod \ \dfrac{m_2}{\text{gcd}(m_1,m_2)}$$

当 $\dfrac{(a_2-a_1)}{gcd(m_1,m_2)}\notin N^{\ast}$ 时显然无解。

将解得的 $k_1$ 带入 $(1)$ 式可以得到 $x$ 的解。易得 $x$ 的通解为

$$x'=x+k\times \text{LCM}(m_1,m_2)\tag{2}$$

$(2)$ 可以转化为：

$$x'\equiv x \ (mod \ \text{LCM}(m_1,m_2)) \tag{3}$$

对第 $1$ 个式子与其它所有式子合并即可得到答案。

可以看出 $(1)$ 的 $x$ 会变成下一个式子中的 $a_{nxt}$ ，所以每次合并得到的 $x$ 是可以递推的，将其记为 $A$。

将 $(3)$ 拓展到 $n$ 个式子全部合并的情况：

$$x\equiv A (mod \ \text{LCM}(m_1,m_2,\ldots,m_n))$$

inline int excrt()
{
    int M=m[1],A=a[1];
    for (int i=2;i<=n;i++)
    {
        int x=0,y=0;
        int g=exgcd(M,m[i],x,y); //a=M,b=m[i],c=a[i]-A; x is ans to gcd(M,m[i])
        if ((a[i]-A)%g) return -1;
        x=(x*(a[i]-A)/g)%(m[i]/g); //get min x;
        A+=x*M;
        M=M*m[i]/g; //M=lcm
        A%=M;
    }
    return (A+M)%M;
}