引例

孙子算经中有一著名问题，今日有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何

这要求我们寻找一个整数 $x$，使其满足以下同余方程组：

我们将这个问题放在整数环 $\mathbb{Z}$ 中进行分析。

中国剩余定理的环论形式

设 $R$ 是一个有单位元的交换环， $I_1,I_2,\dots ,I_k$ 是 $R$ 的一组理想。如果这些理想是两两互素的，即对于任意 $i\ne j$，都有 $I_i+I_j=R$，那么存在一个自然的环同构： $R/\left({\bigcap }_{i=1}^k{I}_i\right)\cong {\prod }_{i=1}^k(R/I_i)$ 这个同构映射由 $\varphi :x+\bigcap I_i\mapsto (x+I_1,x+I_2,\dots ,x+I_k)$ 给出。 在我们的问题中，$R=\mathbb{Z}$，理想分别是 $I_1=3\mathbb{Z}$, $I_2=5\mathbb{Z}$, $I_3=7\mathbb{Z}$。 互素验证：在整数环 $\mathbb{Z}$ 中，两个理想 $m\mathbb{Z}$ 和 $n\mathbb{Z}$ 是互素的，当且仅当 $\gcd (m,n)=1$。因为 $\gcd (3,5)=1,\gcd (3,7)=1,\gcd (5,7)=1$，所以这三个理想是两两互素的。 理想的交：在 $\mathbb{Z}$ 中，${\bigcap }_{i=1}^k{n}_i\mathbb{Z}=\text{lcm}(n_1,\dots ,n_k)\mathbb{Z}$。因为 3, 5, 7 两两互质，所以 $\text{lcm}(3,5,7)=3\times 5\times 7=105$。因此，$\bigcap I_i=105\mathbb{Z}$。

通解的构造

CRT 的标准证明是构造性的，这个构造过程本身就给出了求解方法。我们的目标是构造一个解 $x$。 我们寻找三个特殊的整数 $e_1,e_2,e_3$，它们构成了正交幂等元的基础： $e_1\equiv 1(\mathrm{mod}3)$, $e_1\equiv 0(\mathrm{mod}5)$, $e_1\equiv 0(\mathrm{mod}7)$ $e_2\equiv 0(\mathrm{mod}3)$, $e_2\equiv 1(\mathrm{mod}5)$, $e_2\equiv 0(\mathrm{mod}7)$ $e_3\equiv 0(\mathrm{mod}3)$, $e_3\equiv 0(\mathrm{mod}5)$, $e_3\equiv 1(\mathrm{mod}7)$ 一旦找到它们，解就可以直接构造出来： $x=2\cdot e_1+3\cdot e_2+2\cdot e_3$ 这个构造的巧妙之处在于，当我们对 $x$ 模 3 时，$e_2,e_3$ 项都为 0，只剩下 $2\cdot e_1\equiv 2\cdot 1\equiv 2(\mathrm{mod}3)$。同理可验证模 5 和模 7 的情况。

我们求得一个特解 $x=233$。 根据中国剩余定理，解在模 $N=3\times 5\times 7=105$ 的意义下是唯一的。这意味着所有解构成了理想 $105\mathbb{Z}$ 的一个陪集，即 $233+105\mathbb{Z}$。 用同余式表达，通解为： $x\equiv 233(\mathrm{mod}105)$

特解的求法

扩展欧几里得算法

Tip

扩展欧几里得算法的本质，是对欧几里得算法求最大公约数过程的逆向追踪。欧几里得算法通过一系列的除法，将 $gcd(a,b)$表达为越来越小的余数的线性组合。扩展算法则通过回代，将这个最终的 gcd 重新表达为原始输入 $a$ 和 $b$ 的一个特定线性组合。从代数结构上看，它为贝祖等式 $ax+by=gcd(a,b)$ 提供了一个构造性证明，并揭示了理想 $aZ+bZ$的生成元 $gcd(a,b)$。

1. 理论基础：贝祖等式

该算法旨在解决一个基本的数论问题：为给定的整数 $a$ 和 $b$，寻找一对整数解 $(x,y)$。

(线性丢番图方程)

形如 $ax+by=c$ 的方程，其中 $a,b,c$ 为已知整数， $x,y$ 为未知整数，被称为。

扩展欧几里得算法专注于求解当 $c=\gcd (a,b)$ 时的特例，其解的存在性由以下基本定理保证。

贝祖等式

对于任意非零整数 $a$ 和 $b$，存在整数 $x$ 和 $y$，使得： $ax+by=\gcd (a,b)$ 特别地，若 $a$ 与 $b$ 互素，即 $\gcd (a,b)=1$，则方程 $ax+by=1$ 必有整数解。此性质是计算模逆元的理论基石。

2. 算法描述

2.1 正向阶段：欧几里得除法

对整数 $a$ 和 $b$ (不妨设 $a>b>0$)，执行标准的欧几里得算法，生成一个余数序列 $r_i$ 和商序列 $q_i$：

最后一个非零余数 $r_k$ 即为 $\gcd (a,b)$。

2.2 逆向阶段：回代求解

此阶段的目标是将 $\gcd (a,b)=r_k$ 表达为 $a$ 和 $b$ 的线性组合。

1. 起始方程: 从倒数第二个除法式出发，将 $r_k$ 分离出来： $$r_k=r_{k-2}-q_k{r}_{k-1}$$
2. 逐级回代: 利用前一个除法式，将 $r_{k-1}$ 替换为 $r_{k-3}$ 和 $r_{k-2}$ 的表达式。持续此过程，依次消去 $r_{k-1},r_{k-2},\dots ,r_1$，直到表达式中只含有 $a$ 和 $b$。
3. 最终形式: 经过反复代换与合并，最终得到形如 $r_k=X\cdot a+Y\cdot b$ 的等式。此时，$(X,Y)$ 即为方程 $ax+by=\gcd (a,b)$ 的一组特解。

3. 示例

示例 1：求解 $35x+12y=1$ 的特解

3.1.1 正向欧几里得除法

可得 $\gcd (35,12)=1$。

3.1.2 逆向回代

从方程 $(2)$ 开始：

利用方程 $(1)$ 中 $11=35-2\cdot 12$ 进行回代：

因此，特解为 $(x_0,y_0)=(-1,3)$。

特解的构造：核心思想

在 CRT 的构造性证明中，我们要做的是： 在积模下，构造一组“正交幂等元” ，使它们在各自模数上为 1，在其他模数上为 0。

一般构造公式

设
$N=n_1{n}_2\cdots n_k,N_i=\frac{N}{n_i}.$ 因为 $n_i$两两互素，$N_i$与 $n_i$互素，因此存在逆元： $N_i^{-1}(\mathrm{mod}{n}_i)$ 于是可以构造： $e_i=N_i\cdot (N_i^{-1}\mathrm{mod}{n}_i).$ 这就是 CRT 特解构造的本质。

回到原题

以原问题为例有

我们考虑$N_1$ 有:$N_1^{-1}=2$(由拓展欧几里得算法给出) 则可以求得$e_1=35\cdot 1=70$ 同理可以求得$e_2=21,e_3=15$

构造特解