使用中国剩余定理解同余方程组

中国剩余定理可求解如下形式的一元线性同余方程组（其中 $n_1,n_2,\cdots ,n_k$ 两两互质）：

$$\{\begin{array}{ll}x& \equiv a_1(\mathrm{m}\mathrm{o}\mathrm{d}{n}_1)\\ x& \equiv a_2(\mathrm{m}\mathrm{o}\mathrm{d}{n}_2)\\ & ⋮\\ x& \equiv a_k(\mathrm{m}\mathrm{o}\mathrm{d}{n}_k)\end{array}$$

求解过程

1. 计算所有模数的积 $n$；
2. 对于第 $i$ 个方程：
   1. 计算 $m_i=\frac{n}{n_i}$；
   2. 计算 $m_i$ 在模 $n_i$ 意义下的逆元 $m_i^{-1}$；
   3. 计算 $e_i=m_i{m}_i^{-1}(\mathrm{m}\mathrm{o}\mathrm{d}n)$.
3. 方程组在模 $n$ 意义下的唯一解为：$x={\sum }_{i=1}^k{a}_i{e}_i(\mathrm{m}\mathrm{o}\mathrm{d}n)$.

求解得关键就是找出一组 $e_i(\mathrm{m}\mathrm{o}\mathrm{d}n)$，使得 $e_i\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{n}_i)$，并且对于 $j\ne i$, $e_i\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{n}_j)$. 通过上面得方法找出的 $e_i$ 满足这些条件，因为：

• $e_i$ 中含有 $m_i$，而 $m_i$ 含有其他 $n_j$ 的因子，所以 $e_i\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}{n}_j)$.
• 因为 $m_i^{-1}$ 是 $m_i$ 在模 $n_i$ 意义下的逆元，所以 $e_i=m_i{m}_i^{-1}=1(\mathrm{m}\mathrm{o}\mathrm{d}{n}_i)$.

这一组 $e_i(\mathrm{m}\mathrm{o}\mathrm{d}n)$ 作为基，保证 $a_i{e}_i$ 模 $n_i$ 为 $a_i$，而其他均为 $0$. 通过设定在不同基上的坐标 $a_i$ 可以单独控制模 $n_i$ 余下的值，而不会影响其他模数 $n_j$ 余下的值.

典型示例

$$\{\begin{array}{l}x\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}3)\\ x\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}5)\\ x\equiv 2(\mathrm{m}\mathrm{o}\mathrm{d}7)\end{array}$$

解：

模数两两互质，它们的积 $n=3\times 5\times 7=105$.

计算 $m_i$：$m_1=35,m_2=21,m_3=15$.

计算 $m_i^{-1}$：$35x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}3),21x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}5),15x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}7)$.

$2x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}3),1x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}5),1x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}7)$.

解得 $m_1^{-1}=2,m_2^{-1}=1,m_3^{-1}=1$.

计算 $e_i$：$e_1=70,e_2=21,e_3=15$.

解为 $x=2\times 70+3\times 21+2\times 15=23(\mathrm{m}\mathrm{o}\mathrm{d}105)$.

模数并非两两互素的情况

如果方程组模数并非两两互素，将模数进行因式分解，将一个方程变为多个方程，其模数为原来模数的因子（这些因子之间要两两互素，即素分解）.

例如 $x\equiv 7(\mathrm{m}\mathrm{o}\mathrm{d}12)$ 可以分解为

$$\{\begin{array}{l}x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}3)\\ x\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}4)\end{array}$$

$x$ 的系数不为一的情况

如果方程组中方程的系数不为一，那么可以两边同时乘以系数的逆，把 $x$ 的系数化为一.

例如

$$\begin{gathered} 5x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}7) \\ 3\cdot 5x\equiv 3\cdot 1(\mathrm{m}\mathrm{o}\mathrm{d}7) \\ x\equiv 3(\mathrm{m}\mathrm{o}\mathrm{d}7) \end{gathered}$$

$x$ 的次数不为一的情况

使用费马小定理降次.

若出现 $x^2\equiv 1$，将其拆开成两个方程组，两个方程组其他方程相同，而这个方程分别为 $x\equiv 1$ 和 $x\equiv -1$.