中国剩余定理

中国剩余定理

一、问题的引入

• 一个整数除以3余2、除以5余3、除以7余2，求这个整数？答案：23

• 所谓中国剩余定理基本思想：知道一个整数对于几个不同的模数的余数，那么可以推断出该整数对于这些模数的最小非负整数解。

二、拓展欧几里得求逆元

逆元定义：如果一个线性同余方程$ax\equiv 1(modb)$则称 x 为 $amodb$ 的逆元，记作$a^{-1}$

拓展欧几里得算法核心方程：$$ax+by=d=gcd(a,b)$$
$$\begin{array}{rlr}& 根据逆元等式：ax\equiv 1(modb)[此时a、b为已知量,x为a的逆元a^{-1}]& \\ & 转化ax\equiv 1(modb)⟹【ax=nb+1】⟹【ax+n^{\prime }b=1】(n=-n^{\prime })& \end{array}$$
将上述逆元的定义方程进行转化后我们来对比转化方程与拓展欧几里得核心方程
$$\begin{array}{rl}& (1)ax+bn=1【逆元转化方程】\\ & (2)ax+by=gcd(a,b)【拓展欧几里得核心方程】\end{array}$$
可以看到上述两方程的格式不能说相似，只能说一模一样。只需要使用拓展欧几里得算法对互质的两个数求出一组解$(x,y)$

就可以获得逆元了。

三、中国剩余定理的原理

我们继续考虑上述问题：
$$\begin{gathered} 求整数X除以3余2、除以5余3、除以7余2。转化为下述公式: \\ X\%3=2 \\ X\%5=3 \\ X\%7=2 \end{gathered}$$
如果可以找到三个整数 $X_1、X_2、X_3$ 并且满足下述的算式
$$\{\begin{array}{l}{X}_1\%3=2\\ X_1\%5=0\\ X_1\%7=0\end{array}\{\begin{array}{l}{X}_2\%3=0\\ X_2\%5=3\\ X_2\%7=0\end{array}\{\begin{array}{l}{X}_3\%3=0\\ X_3\%5=0\\ X_3\%7=2\end{array}$$
那么 $X$ 可以由这三个整数 $X_1、X_2、X_3$ 构成
$$X=X_1+X_2+X_3$$
继续将上述的 $X_1、X_2、X_3$ 分解为子问题
$$\{\begin{array}{l}{Y}_1\%3=1\\ Y_1\%5=0\\ Y_1\%7=0\end{array}\{\begin{array}{l}{Y}_2\%3=0\\ Y_2\%5=1\\ Y_2\%7=0\end{array}\{\begin{array}{l}{Y}_3\%3=0\\ Y_3\%5=0\\ Y_3\%7=1\end{array}$$
于是 $X_1、X_2、X_3$ 就可以由对应的Y构成
$$\begin{gathered} X_1=2Y_1 \\ {X}_2=3Y_2 \\ {X}_3=2Y_3 \end{gathered}$$
所以根据上述的分解，我们最后得到了
$$X=2Y_1+3Y_2+2Y_3$$
我们以其中一个子问题为例求解
$$\begin{gathered} Y_1\%3=1 \\ {Y}_1\%5=0 \\ {Y}_1\%7=0 \end{gathered}$$
根据上述等式不难知道 $Y_1$ 一定是 $5\times 7=35$ 的倍数，于是我们令 $Y_1=35k$

那么就有 $35k\equiv 1(\mathrm{mod}3)$，这时 $k$ 就是 $5\times 7$ 模 3 的逆元，记 $k=[35^{-1}{]}_3$ 那么 $Y_1=5\times 7\times [35^{-1}{]}_3$

因此将所有子问题求解得下述等式
$$\{\begin{array}{l}{Y}_1=5\times 7\times [(5\times 7{)}^{-1}{]}_3并且[(5\times 7{)}^{-1}{]}_3=2\\ Y_2=3\times 7\times [(3\times 7{)}^{-1}{]}_5并且[(3\times 7{)}^{-1}{]}_5=1\\ Y_3=3\times 5\times [(3\times 5{)}^{-1}{]}_7并且[(3\times 5{)}^{-1}{]}_7=1\end{array}$$
由此可以得到最终式子还要mod$(3\times 5\times 7)$因为要求最小整数
$$X=2\times (5\times 7\times [(5\times 7{)}^{-1}{]}_3)+3\times (3\times 7\times [(3\times 7{)}^{-1}{]}_5)+2\times (3\times 5\times [(3\times 5{)}^{-1}{]}_7)(\mathrm{mod}3\times 5\times 7)$$
逆元怎么求？看上述第二节的内容
$$\begin{gathered} [(5\times 7{)}^{-1}{]}_3=2 \\ [(3\times 7{)}^{-1}{]}_5=1 \\ [(3\times 5{)}^{-1}{]}_7=1 \end{gathered}$$
所以$X=(2\times 5\times 7\times 2)+(3\times 3\times 7\times 1)+(2\times 3\times 5\times 1)(\mathrm{mod}105)=(140+63+30)(\mathrm{mod}105)=23$