中国剩余定理

定理：设gcd (a, n) = 1，n > 0，则同余式：

a x ≡ b mod n

恰有一个解。

而 x = ba^𝜑(n)－1 就是其唯一解。 ( a^-1 ≡ a^𝜑(n)－1 mod n )

其实可以类比求逆元，当a、n互质，b=1时该定理退化为费马小定理，此时恰有一个解，也就是a^-1。

进而有中国剩余定理。

设自然数m1 , m2 , …, m r两两互素，记 M = m1 m2 ⋯ m r ，则同余方程组：

$\left\{\begin{array}{c} x \equiv b_{1}\left(\bmod m_{1}\right) \\ x \equiv b_{2}\left(\bmod m_{2}\right) \\ \vdots \\ x \equiv b_{r}\left(\bmod m_{r}\right) \end{array}\right.$

在模M同余的意义下有唯一解:

$x$ $\equiv$ $\sum_{i=1}^{r}$ $b_ {i}$ $M_ {i}$ $y_ {i}$ ( $\bmod$ $M$ )

式中 $M_ {i}$ = $\frac {M}{m_ {i}}$ , $y_{i}$ = $M_ {i}^ {-1}$ ( $mod$ $m_ {i}$ )(1 $\leqslant$ $i$ $\leqslant$ r)

即 $x_ {0}$ = $b_ {1}$ $M_ {1}$ $y_ {1}$ + $b_ {2}$ $M_ {2}$ $y_ {2}$ + $\cdots$ + $b_ {r}M_{r} y_{r}$ 为该同余方程组的唯一解。

根据同余方程组，我们可以很方便的求得b、M的值，但是y的值需要对对应的M值求逆元得到，所以我们要做的实际上就是求解 $M_{i}y_{i}\equiv1\bmod m_{i}$

而求解逆元的方法可参考我们在文首提到的费马小定理，有 $y_{i}=M_{i}^{φ(m_i)-1}\equiv\bmod m_i$

其中 $φ(m_i)$ 是m的欧拉函数。如果m是质数，那么它的欧拉函数就等于 $\varphi(m) = m - 1$ ；如果m是合数，那么 $\varphi(m) = \varphi(p_1) \varphi(p_2)$ ，即 $\varphi(m)=(p_1-1)(p_2-1)$ ，或者 $\phi(n)=n\left(1-\frac{1}{p_{1}}\right)\left(1-\frac{1}{p_{2}}\right) \ldots\left(1-\frac{1}{p_{r}}\right)$