python/TangDou/AcWing/NumberTheory/合并同余方程.md

https://blog.csdn.net/sleepiest/article/details/81865741

这个不看懂，没法看 https://www.luogu.com.cn/blog/blue/kuo-zhan-zhong-guo-sheng-yu-ding-li

1 导语

同余方程组，是形如

\large x \equiv x_1 (mod \ \ p_1 ) \\
\large x \equiv x_2 (mod \ \ p_2 ) \\
\large ...  \\
\large x \equiv x_n (mod \ \ p_n )$$
的方程组。

当$\large p_1,p_2,...,p_n$两两互质的时候，我们可以使用中国剩余定理。但如果他们不互质呢？

### 2 裴蜀定理与扩展欧几里得算法
这里先介绍一下**裴蜀定理与扩展欧几里得算法**作为**铺垫**。

裴蜀定理：对于不完全为 的非负整数 ， 表示 的最大公约数。则必然存在整数对 ，使得
$$\large (a,b)=ax+by$$
具体证明略。

扩展欧几里得算法则是对这个方程求解的算法。

### 3 合并同余方程组
比如我们先合并前两个方程。
$$\large x \equiv x_1 (mod \ \ p_1 ) \\ \large x \equiv x_2 (mod \ \ p_2 )$$

根据余数的定义，我们可以将方程改写为
$$\large x=x_1 \times k_1 +p_1 \ \  (1) \\
x=x_2 \times k_2 +p_2 \ \  (2) 

合并(1),(2)得：

\large x_1*k_1-x_2*k_2=p_2-p_1 \ \ (3) 

这是一个关于k_1，k_2的不定方程，当\large (p_2—p_1)\% gcd(x_1，x_2)=0时有解。

当有解时，用扩展欧几里得可求得 k_{1} 的一个特解，设为 k^{'} ， 那么 k_{1} 的通解为：\large k_{1} = k^{'}+ t * (x_{2} / gcd(x_{1},x_{2}))

将 k_{1} 代回到式1中可得：

\large x_1*(k^{'}+t*(x_2/gcd(x_1,x_2)))+p_1=x \\
 \Rightarrow \\
\large x_1*x_2 /gcd(x_1,x_2)*t+x_1*k^{'}+p_1= x $$

可以发现：$\large x_{1} *x_{2} / gcd(x_{1},x_{2})$是$x_{1} ,x_{2}$ 的最小公倍数，可以转换表示为 $[x_{1}，x_{2}]$

$$\large [x_1,x_2]*t+x_1*k^{'}+p_1=x $$

所以合并式$(1)，(2)$两个同余组，变为：
$$\large x ≡ x_{1} * k^{'} + p_{1} (mod  [x_{1}，x_{2}])$$

$\large x_{1}， p_{1}$ 都是已知的，只需求某个特解 $\large k^{'}$  和 $\large [x_{1}，x_{2}]$ 即可。

### 4 举个栗子
$$ \large
  \left\{\begin{matrix}
   x \equiv 2(mod \ 4) \\ 
   x \equiv 4(mod \ 6) \\ 
  \end{matrix}\right.  \Rightarrow  x \equiv 10 (mod \ 12)

由(1)式，手动模拟一些x,得：6,10,14,18,22,26,30,34,38,42,46...

由(2)式，手动模拟一些x,得：10,16,22,28,34,40,46,...

可以发现，这两个式子要想得到的公共解，其实是一组解，它们是：\large 10,22,34,46,...

找一下规律，就是从\large 10开始，循环节为\large 12，也就是原来两个模数\large p_1,p_2的\large [p_1,p_2]。