关于中国剩余定理的菜鸟级介绍，不妥之处还望斧正

本文不细究各种数的取值范围，烦请读者自己斟酌

前人之述备矣。然则北通巫峡，南极潇湘，迁客骚人，多会于此，览物之情，得无异乎？

1.一元一次同余方程组求解

1.1. 作弊法

$x ≡ 2 (mod\ 5)$

$x ≡ 3 (mod\ 7)$

首先学会用sage(验)算：

（有手就行

sage: crt([2,3],[5,7])
17

1.2. 解析法

然后学会套公式算

（有手就行

对于

$x ≡ a (mod\ p)$

$x ≡ b (mod\ q)$

其中p与q互素

可得

$x = aqq^{-1} + bpp^{-1}$ (*)

其中$q*q^{-1} ≡ 1\ mod\ p, p*p^{-1} ≡ 1\ mod\ q$

最后证明一下$x$是$mod\ n$下的唯一解，其中$n=pq$。

什么意思呢？

不难看出，(*)式中$q$和$p$的逆元不唯一

也就是说$x$不唯一，在茫茫整数域中有无限个$x$

而它们有什么共同点呢？这是一个很自然的问题，好比一元二次方程中两个根的解析关系（韦达定理）

同样很自然地，我们会觉得它们在$mod\ n$下同余

碰巧这个直觉是对的，并且很有用，以下是证明

证：

假设$\exist y \not= x$ 符合(*)式，

则有

$y ≡ a (mod\ p)$

$y ≡ b (mod\ q)$

则 $\exist m_1,m_2 \in Z$ 使得

$y = a + m_1p = b + m_2q$

显然有

$(y-x) = tp = sq$ 其中$t,s \in Z$

又 $gcd(p,q) = 1$

$∴\exist k \in Z$ 使得

$tp = (kq)p = (kp)q = sq$

因此 $y ≡ x (mod\ n)$

所以我们可以得到

$x ≡ aqq^{-1} + bpp^{-1}\ (mod\ n)$

1.3. 一个小细节

为什么要限制p和q互素？

答案很简单，为了避免出现零元导致没有解析解

2.整数群下的乘法逆元求解

上文出现了p和q分别关于q和p的乘法逆元，然而并没有说怎么算

以下是方法

2.1.作弊法

推一下大佬的blog，非常详细：

luo41:乘法逆元求法总结

2.2.裴蜀定理与手动矩阵求解

我写完这部分才发现luo41大佬已经写得非常详尽了，在此还是强推大佬的blog。

luo41:乘法逆元求法总结

—————————————–——以下是原文案——————————————————-

下面利用裴蜀定理来求解（简单的）乘法逆元

$Bézout$ 定理 (裴蜀定理)
设 $a$ 和 $b$ 为非零整数，存在整数 $r$ 和 $s$ 使得：

$gcd(a, b) = ar + bs$
而且，$a$ 与 $b$ 的最大公因子是惟一的。称 $r$ 和 $s$ 为 $Bézout$ 系数

∵gcd(p,q) = 1

∴pr+qs = 1

显然有

$(pr+qs)\ mod\ q = pr ≡ 1 (mod\ q)$

$(pr+qs)\ mod\ p = qs ≡ 1 (mod\ p)$

不难看出，r和s分别就是$p\ mod\ q$和$q\ mod\ p$的乘法逆元

那么，怎么计算出来呢，很简单，利用gcd算法建立矩阵

$\begin{bmatrix} 1 & 0 & p \\ 0 & 1 & q \end{bmatrix}$

意思是

$1*p+0*q = p$

$0*p + 1*q = q$

对最后一列执行gcd(p,q)

具体做法就是

用第一行减去第二行，得到一个新的行。然后把第一行用第二行替换，第二行用新的一行替换,

得到一个新的矩阵：

$\begin{bmatrix} 0 & 1 & q \\ 1 & -1 & (p-q) \end{bmatrix}$

适当进行行调整并不断迭代

最终得到答案(最后一行)

$\begin{bmatrix} r & s & 1 \end{bmatrix}$

乘法逆元get

3.代数视角下的中国剩余定理

偷懒复制下CINTA里的定义

定理 10.4. 中国剩余定理的代数版本
设 n = p*q，p > 1 和 q > 1 是两个互素的正整数。则 $Z_n \cong Z_p × Z_q$

且 $Z^∗_n \cong Z^∗_p × Z^∗_q$。

证明略。

对于定理中的乘号，是我们略有耳闻的笛卡尔积：

给定两个群 $\mathbb{G}$ 和 $\mathbb{H}$，记 $\mathbb{G}$ × $\mathbb{H}$ 为集合 $\mathbb{G}$ 与集合 $\mathbb{H}$ 的笛卡尔乘积，并定义集合 $\mathbb{G}$ × $\mathbb{H}$ 中元素的乘法操作 · 为： $(g1, h1) · (g2, h2) = (g1g2, h1h2)$ 。 可验证，$\mathbb{G}$ × $\mathbb{H}$ 是群，并称为 $\mathbb{G}$ 与 $\mathbb{H}$ 的 直积（direct product）

简而言之，笛卡尔积构造了两个群之间元素的一系列序对，给这一系列序对 定义一个乘法操作$·$ ，可以构造一个（由这些序对形成的）群。

所以说 $\cong$ 两边实际上是两个群。

那么，构造一个这样的同构有什么用呢？

很显然，利用代数版本的CRT能把一个规模为n的问题分解为规模p和q的问题，前后规模相差了 $(n-(p+q))$ ！如果能继续分解的话，对于效率的增进是显著的。

不难发现，在解某些小学奥数题时，我们能利用它显著减少计算量：

m0d1:利用中国剩余定理求解模指数运算问题

以上。