中国剩余定理解析_中国剩余定理详解

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

孙子问题

最早，在《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？用白话描述就是，现在有一个数不知道是多少，只知道这个数除以3余2，除以5余3，除以7余2， 问这个数是多少？

上面的问题可以转换为以下这样一个方程组:

$$\{\begin{array}{l}xmod3=2\\ xmod5=3\\ xmod7=2\end{array}$$

其中这个$x$就是我们要求的数。而中国剩余定理就是用来解决上述形式的方程组的$x$解的。

解答讲解

在开始解答这个问题之前，我们先来了解一下几个数论基本知识。

基本等式

$(1)amodb=(a+k\ast b)modb$

$(2)(a\ast k)modb=k\ast (amodb)$

需要注意:$a\equiv b(modc)$的意思是$amodc=bmodc$

在了解两个基本等式之后我们就可以对上述方程组做一些变换了:
$$\{\begin{array}{l}x=k_1\ast 3+2\\ x=k_2\ast 5+3\\ x=k_3\ast 7+2\end{array}$$

直接看上面的方程组，好像直接求解出$k_1、k_2、k_3$不太现实，所以我们需要另寻出路。在这里我们先假设三个数，分别是$n_1、n_2、n_3$,满足一下条件:
$$\{\begin{array}{l}{n}_{1}mod3=2\\ n_{2}mod5=3\\ n_{3}mod7=2\end{array}$$
假如$n_2、n_3$均能整除3的话，那么按照等式$(1)$就有:

$$\{\begin{array}{l}{n}_2=k_2^{\prime }\ast 3\\ n_3=k_3^{\prime }\ast 3\end{array}$$

$$\begin{gathered} (n_1+k_2^{\prime }\ast 3+k_3^{\prime }\ast 3)mod3=n_{1}mod3=2 \\ (n_1+n_2+n_3)mod3=2 \end{gathered}$$

那么我们继续假如$n_1、n_3$能被5整除，$n_1、n_2$能被7整除，那么就有:
$$\{\begin{array}{l}(n_1+n_2+n_3)mod3=2\\ (n_1+n_2+n_3)mod5=3\\ (n_1+n_2+n_3)mod7=2\end{array}$$

对比题目中的方程组，可以看出只要满足以下条件就能使我们需要求解的$x=(n_1+n_2+n_3)$:

1. $n_1$除以3余2，且是5和7的公倍数。
2. $n_2$除以5余3，且是3和7的公倍数。
3. $n_3$除以7余2，且是3和5的公倍数。

我们只需要将$n_1、n_2、n_3$求出来后相加即可得我们想求的$x$值。不过，这只是其中一个解，并不是最小解。要求最小解我们还需要除以$n_1、n_2、n_3$的最大公约数。

这里呢，我们以$n_1$求解为例，$n_2、n_3$求解过程类似。

求解$n_1$过程

首先我们先罗列一下基本约束条件:

$\{\begin{array}{l}{n}_{1}mod3=2\\ n_1=5\ast k_2^{\prime }\\ n_1=7\ast k_3^{\prime }\end{array}$

根据等式$(2)$，可以得到:

$n_{1}mod3=2\ast (\frac{n_1}{2}mod3)=2$

$\frac{n_1}{2}mod3=1$

如果$\frac{n_1}{2}$是5、7的整数倍，那么$n_1$自然也是5、7的整数倍。不过在这里呢，我们并没有从5和7的公倍数中直接找一个除以3余2的数，而是先找一个除以3余1的数，再乘以2。也就是先求出5和7的公倍数模3下的逆元，再用逆元去乘余数。具体过程如下:参考来源

推算过程如下:

$首先我们令K=\frac{n_1}{2},$

$$\begin{gathered} 因为 \\ Kmod3=1(K是5和7的整数倍), \\ 所以 \\ gcd(5\ast 7,3)=1,即35与3互质，由拓展欧几里得算有: \\ K\equiv 1(mod3)\Rightarrow K=a\ast x=(5\ast 7)\ast x\equiv 1(mod3) \\ 35\ast x+3\ast y=1\Rightarrow 整数解为:\{\begin{array}{l}x=2,\\ y=-23,\end{array} \\ 可求得a的逆元x=2,则K=70\Rightarrow n_1=2\ast K=140 \end{gathered}$$

$类似,可求出n_2=63，n_3=30\Rightarrow x=(n_1+n_2+n_3)=233$

$不过此时并不是最小数，我们还需要将233÷(3、5、7{)}_{最大公约数105}=23，这才是符合条件的最小数$

最大公倍数=各个数的乘积$÷$最大公约数，最大公约数可使用辗转相除法获取(欧几里得算法)

中国剩余定理公式

设正整数$m_1,m_2,...,m_k,$两两互素，则同余方程组:
$$\{\begin{array}{l}x\equiv a_1(mod{m}_1)\\ x\equiv a_2(mod{m}_2)\\ ......\\ x\equiv a_k(mod{m}_k)\end{array}$$
有整数解。并且在模$M=m_1\ast m_2\ast ...\ast m_k$下的解是唯一的，解为

$x\equiv (a_1{M}_1{M}_1^{-1}+a_2{M}_2{M}_2^{-1}+...+a_k{M}_k{M}_k^{-1})modM$

其中$M_i=\frac{M}{m_i}$，而$M_i$模$m_i$的逆元。

关于扩展欧几里得算法

参考文章:欧几里德算法与扩展欧几里德算法

用途

用来求解形如$ax+by=c(a,b,c\in Z)$的方程的一组整数解.。

使用条件

$cmodgcd(a,b)=0,gcd(a,b)表示a/b的最大公约数$

求解过程

$$求解方程:ax+by=gcd(a,b)$$

$(1)当b=0时，原方程可化为ax=gcd(a,0)\Rightarrow 解得:\{\begin{array}{l}x=1\\ y=0\end{array}$
$(2)设a^{\prime }=b,b^{\prime }=amodb,有如下方程:$

$$\{\begin{array}{l}{a}^{\prime }{x}^{\prime }+b^{\prime }{y}^{\prime }=gcd(a^{\prime },b{}^{\prime })=gcd(b,amodb)\\ ax+by=\gcd (a,b)\end{array}$$

$另有恒等式:gcd(a,b)=gcd(b,amodb)，则:$

$ax+by=a^{\prime }{x}^{\prime }+b^{\prime }{y}^{\prime }=b{x}^{\prime }+(amodb)y^{\prime }=b{x}^{\prime }+(a-\lfloor \frac{a}{b}\rfloor b)y^{\prime }$
$整理得:$
$$\begin{gathered} ax+by==b{x}^{\prime }+(a-\lfloor \frac{a}{b}\rfloor b)y^{\prime } \\ \Downarrow \\ \{\begin{array}{l}x=y^{\prime }\\ y=x{}^{\prime }-\lfloor \frac{a}{b}\rfloor y{}^{\prime }\end{array} \end{gathered}$$
通过上述这个解可知道，如果反复迭代递归，最终一定会到达临界条件$b=0$,即情况$(1)$,从而计算出最终值。