中国剩余定理

· · 个人记录

乘法逆元

若整数 b，m 互质，并且对于任意的整数 a，如果满足\ b|a，则存在一个整数 x，使得 a/b≡a×x(mod \ m)，则称 x 为 b 的模 m 乘法逆元，记为 b^{-1}(mod \ m),b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，b^{m-2} 即为 b 的乘法逆元。

中国剩余定理

对于方程:

\left\{ \begin{matrix} x \equiv b_1(mod \ a_1)\\ x \equiv b_2(mod \ a_2)\\ x \equiv b_3(mod \ a_3)\\ \cdots \\ x \equiv b_n(mod \ a_n) \end{matrix} \right.

解方程的方法

由于我们一般求的是最小正整数解，故这里只讨论\最小整数数解的求法。 我们先来讨论 a_i 彼此互质的情况（我们称这种算法为 CRT (Chinese Remainder Theorem)，即中国剩余定理（算法导论中将其翻译为“中国余数定理”））。 引理：（中国剩余定理）若两个互质的正整数 n,m，若两个整数 a,b 满足

证明考虑反证法,假设$\exists 0 \leq x_1,x_2 \leq nm$,使得$x_1,x_2$关于$n,m$同余 ,假设$x_1<x_2$,令$k=x_2-x_1$,显然$n|k,m|k$,所以$k_{min}=lcm(n,m)=nm,x_2=x_1+k \geq nm$,矛盾。 由数学归纳法可知原方程组在$[0,\prod_{i=1}^{n}a_i)$内有唯一解。 构造出原方程的一个解。 $x=\sum_{i=1}^{n}k_i\frac{\prod_{j=1}^{n}a_j}{a_i}$,其中$k_i$是满足$k_i\frac{\prod_{j=1}^{n}a_j}{a_i} \equiv b_i(mod \ m)

设m_i=\frac{\prod_{j=1}^{n}a_j}{a_i},因为a_i两两互质,m_i必定与a_i互质 故存在模a_i意义下m_i的逆元,设为t_i，t_im_i \equiv 1(mod \ a_i) b_it_im_i\equiv b_i(mod\ a_i),又k_im_i\equiv b_i(mod\ a_i),

b_it_i\equiv k_i(mod\ a_i),k_i$最小为$b_it_i mod\ a_i

故方程的一个解为x= \sum_{i=1}^{n}(b_it_i\ mod \ a_i) \times m_i

EXCRT

然而在不保证 a_i 两两互质时，又是另一种情况。
由于 a_i 之间可能不互质，故我们可能找不到某个 m_i 在模 a_i 意义下的逆元，故我们得另辟蹊径。 不妨从小规模的问题开始考虑，考虑对于仅由两个线性同余方程组成的方程组：

\begin{cases} x \equiv b_1 \pmod{a_1} \\ x \equiv b_2 \pmod{a_2} \end{cases}

化成等式：

\begin{cases} x = b_1 + k_1a_1 \\ x = b_2 + k_2a_2 \end{cases}

不难发现b_1 + k_1a_1 = b_2 + k_2a_2。
用exgcd求出k1,k2。有解条件： \gcd(a1,a2)|b2-b1 。
设 x_0=b_1+a_1k_1，由于lcm(a1,a2)|a1,lcm(a2,a2)|a2。
方程通解为：

x=x_0+lcm(a1,a2)k,\iff x \equiv x_0 \pmod{lcm(a1,a2)}