孙子问题
现在有这样一个式子
\begin{cases} x \bmod 3 = 2 \\ x \bmod 5 = 3 \\ x \bmod 7 = 2 \end{cases}
现在让你求 x
首先要理解下面的两个式子
(1) a \bmod b = (a + k \times b) \bmod b
(2) (a \times k) \bmod b = (k \times a) \bmod b
以及同余符号的含义
a \equiv b (\bmod c) 的意思和 a \bmod c = b \bmod c 的意思相同
于是我们可以对上面的式子做一个变形
\begin{cases} x = k_1 \times 3 + 2 \\ x = k_2 \times 5 + 3 \\ x = k_3 \times 7 + 2 \end{cases}
然后…把这个式子放在一边
先看这个式子（式子中的 n_1 、 n_2 、 n_3 均为未知数）
\begin{cases} n_1 \bmod 3 = 2 \\ n_2 \bmod 5 = 3 \\ n_3 \bmod 7 = 2 \end{cases}
然后我们进行三次假设
1.假设 n_2 和 n_3 都是 3 的倍数
那么就有
\begin{cases} n_2 = k'_2 \times 3 \\ n_3 = k'_3 \times 3 \end{cases}
用式子(1)可以推出
n_1 + k'_2 \times 3 + k'_3 \times 3 \equiv n_1 (\bmod 3)
带入得
n_1 + n_2 + n_3 \equiv n_1 (\bmod 3)
2.假设 n_1 和 n_3 都是 5 的倍数
那么就有
\begin{cases} n_1 = k'_1 \times 5 \\ n_3 = k'_3 \times 5 \end{cases}
用式子(1)可以推出
n_2 + k'_1 \times 5 + k'_3 \times 5 \equiv n_2 (\bmod 5)
带入得
n_1 + n_2 + n_3 \equiv n_2 (\bmod 5)
3.假设 n_1 和 n_2 都是 7 的倍数
那么就有
\begin{cases} n_1 = k'_1 \times 7 \\ n_2 = k'_2 \times 7 \end{cases}
用式子(1)可以推出
n_3 + k'_1 \times 7 + k'_2 \times 7 \equiv n_1 (\bmod 3)
带入得
n_1 + n_2 + n_3 \equiv n_3 (\bmod 7)
不难看出，当三次假设都成立时，式原子会变成这样
\begin{cases} (n_1 + n_2 + n_3) \bmod 3 = 2 \\ (n_1 + n_2 + n_3) \bmod 5 = 3 \\ (n_1 + n_2 + n_3) \bmod 7 = 2 \end{cases}
此时的 (n_1 + n_2 + n_3) 即为我们想求的 x
于是我们将求 x 的任务转化成了求满足假设的 n_1 、 n_2 、 n_3 的值
以求解 n_1 为例， n_2 、 n_3 所用方法与之相似
先写一下约束条件
\begin{cases} n_1 \bmod 3 = 2 \\ n_1 = k'_2 \times 5 \\ n_1 = k'_3 \times 7 \end{cases}
用一下最开始列出的式子(2)转化一下，可得
n_1 \bmod 3 = 2 \times (\frac{n_1}2 \bmod 3) = 2
\frac{n_1}2 \bmod 3 = 1
于是你可以这样求
先找一个除以 3 余 1 的数，再乘以 2
也就是先求出 5 和 7 的公倍数模 3 下的逆元，再用逆元去乘余数
证明如下
令 X = \frac{n_1}2
\because X \bmod 3 = 1
\therefore gcd(5 \times 7, 3) = 1
由扩展欧几里得算有
X \equiv 1 (\bmod 3) \Longrightarrow X = a \times x = (5 \times 7) \times x \equiv 1 (\bmod 3)
35 \times x + 3 \times y = 1 \Longrightarrow 整数解为 \begin{cases} x = 2 \\ y = -23 \end{cases}
可以求得 a 的逆元 x = 2 则 X = 70 \Longrightarrow n_1 = 2 \times X = 140
类似的，可以求出
n_2 = 63 、 n_3 = 30
而 x 的值就是
(n_1 + n_2 + n_3) \bmod 105 = 23
为什么 \bmod 105 ？
因为 3 5 7的最小公倍数是105啊
中国剩余定理
只有公式的附加品
已知这样的一个同余方程组（其中 m_1 m_2 \cdots m_k 均为质数）
\begin{cases} x \equiv a_1 (\bmod m_1) \\ x \equiv a_2 (\bmod m_2) \\ \cdots \\ x \equiv a_k (\bmod m_k) \end{cases}
我们将求解过程分为 3 步
1.计算 M = m_1 \times m_2 \times \cdots \times m_k
2.对于第 i 个方程：
\hspace{0.5cm} a.计算 n_i = \frac M {m_i}
\hspace{0.5cm} b.计算 n_i 在 \bmod m_i 意义下的逆元 n_i^{-1}
\hspace{0.5cm} c.计算 c_i = n_i \times n_i^{-1}
则 x 在 \bmod M 意义下的唯一解为 x = \sum_{i = 1}^k a_i c_i (\bmod M)