中国剩余定理CRT笔记

描述

假设整数 \(m_1,m_2,\cdots,m_n\) 两两互素，则对于任意的整数 \(a_1,a_2,\cdots,a_n\)，方程组 \[ \begin{cases} x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2}\\ \cdots\\ x\equiv a_n\pmod{m_n} \end{cases} \] 都存在整数解，且若 \(X,Y\) 都满足该方程，则必有 \(X\equiv Y\pmod{M}\)，其中 \(M=\displaystyle\prod_{i=1}^nm_i\) 。

具体而言，\(x\equiv \displaystyle\sum_{i=1}^na_i\times\frac{M}{m_i}\times\left[\left(\frac{M}{m_i}\right)^{-1}\right]_{m_i}\pmod{M}\\\)

这便是中国剩余定理(Chinese remainder theorem, CRT)

求解可以使用以下步骤进行构造：

1. 设 \(M=\displaystyle\prod_{i=1}^nm_i\)，并设 \(M_i=\frac{M}{m_i}\)，即除了 \(m_i\) 以外 \(n-1\) 个数的乘积

2. 设 \(t_i=M_i^{-1}\)，即求 \(M_i\) 对 \(m_i\) 的模反元素

3. 那么方程组的通解即为 \[ x=kM+\sum_{i=1}^na_it_iM_i,k\in\mathrm{Z} \] 在模 \(M\) 的环中，方程组仅有一个唯一整数解 \[ x=\sum_{i=1}^na_it_iM_i\pmod{M} \]

实例

以“物不知数”问题为例，运用中国剩余定理求解。

在该问题中，线性同余方程组为 \[ \begin{cases} x\equiv 2\pmod{3}\\ x\equiv 3\pmod{5}\\ x\equiv 2\pmod{7} \end{cases} \] 其中模数 \(m_1=3,m_2=5,m_3=7\)，得到 \(M=105\)，对应的 \(M_1=35,M_2=21,M_3=15\)，从而得到逆元 \(t_1=2,t_2=1,t_3=1\)

故得到基础解 \[ 70=2\times 35\equiv \begin{cases} 1\pmod{3}\\ 0\pmod{5}\\ 0\pmod{7}\\ \end{cases},\ 21=3\times 7\equiv \begin{cases} 0\pmod{3}\\ 1\pmod{5}\\ 0\pmod{7}\\ \end{cases},\ 15=3\times 5\equiv \begin{cases} 0\pmod{3}\\ 0\pmod{5}\\ 1\pmod{7}\\ \end{cases}\\ \] 将 \(a_1,a_2,a_3\) 与基础解对应相乘并求和，得到方程组的解 \[ 233=2\times 70+3\times 21+2\times 15\equiv \begin{cases} 2\times1+3\times0+2\times0\equiv2\pmod3\\ 2\times0+3\times1+2\times0\equiv3\pmod5\\ 2\times0+3\times0+2\times1\equiv2\pmod7 \end{cases} \] 故方程组通解为 \[ x=233+k\times105,k\in\mathrm{Z} \] 当 \(k=-2\) 时，有最小正整数解 \(x=23\)

扩展

中国剩余定理是适用于 \(m_i\) 两两互素的情况的，如果不互素，需要使用合并方程的思想来转换成两两互素后求解。

证明如下

首先仅考虑方程组中的两个方程 \[ \begin{cases} x\equiv a_1\pmod{m_1}\\ x\equiv a_2\pmod{m_2} \end{cases} \] 那么有 \[ x=k_1m_1+a_1\\ x=k_2m_2+a_2\tag{*} \] 即 \(k_1m_1+a_1=k_2m_2+a_2\)，变形为 \(m_1k_1=(a_2-a_1)+k_2m_2\)，最终得到 \[ m_1k_1=a_2-a_1\pmod{m_2} \] 显然，想要有解，必有 \(\gcd(m_1,m_2)|(a_2-a_1)\)

不妨设 \(d=\gcd(m_1,m_2),c=a_2-a_1\)，则有 \[ \frac{k_1m_1}{d}=\frac{c}{d}\pmod{\frac{m_2}{d}}\\ \Rightarrow k_1=\frac{c}{d}\times\left(\frac{m_1}{d}\right)^{-1}\pmod{\frac{m_2}{d}} \] 令 \(K=\displaystyle\frac{c}{d}\times\left(\frac{m_1}{d}\right)^{-1}\)，则 \(k_1=y\displaystyle\frac{m_2}{d}+K\\\)

代入方程 \((*)\) 得 \[ \begin{aligned} x&=m_1(y\frac{m_2}{d}+K)+a_1\\ &=m_1K+y\frac{m_1m_2}{d}+a_1 \end{aligned} \] 即 \[ x=m_1K+a_1\pmod{\frac{m_1m_2}{d}} \] 即 \[ x\equiv a\pmod{m},\mathrm{其中}\ a=m_1K+a_11,m=\frac{m_1m_2}{d} \] 这样，就将方程组合并成为上面这个方程。

最终，合并 \(k\) 个方程的最小 \(x\) 值为 \(a\mod m\)

例如，因为 \[ 84=2^2\times3\times7,160=2^5\times5,63=3^2\times7 \] 我们通过合并可得 \[ \begin{cases} x\equiv23\pmod{84}\\ x\equiv7\pmod{160}\\ x\equiv2\pmod{63} \end{cases} \ \mathrm{与}\ \begin{cases} x\equiv7\pmod{2^5}\\ x\equiv2\pmod{3^2}\\ x\equiv7\pmod{5}\\ x\equiv23\pmod{7} \end{cases} \ \mathrm{同解} \]

代码

对于 \(m_i\) 互素的情况

import math
import gmpy2

def CRT(alist, mlist):
    M = math.prod(mlist)
    x = 0
    for ai, mi in zip(alist, mlist):
        Mi = M // mi
        d, _, ti = gmpy2.gcdext(mi, Mi)
        if d != 1: raise Exception("Input not palistrwise co-prime")
        x += ai * ti * Mi
    return x % M, M