引入

---

考试的原题忘了，那么我们先来看一个古老的问题：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即求满足以下条件的整数：除以$3$余$2$，除以$5$余$3$，除以$7$余$2$。

该问题最早见于《孙子算经》中，并有该问题的具体解法。

宋朝数学家秦九韶于$1247$年《数书九章》卷一、二《大衍类》对此类问题做出了完整系统的解答。

上面具体问题的解答口诀由明朝数学家程大位在《算法统宗》中给出：

三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便得知。

口胡一下，大概是：$2\times 70+3\times 21+2\times 15=233=2\times 105+23$，故答案为$23$。

可是为什么呢？我们可以用浅显的初等数论 + 线性方程组来解答。

数学定义

---

逆元

---

在学习CRT之前，我们先来了解逆元：

我们先看定义：

对于非零整数$a,m$，如果存在$b$使得$a\times b\equiv 1(\mathrm{mod}m)$，就称$b$是$a$在模$m$意义下的逆元（inverse）。

例如：$5$是$3$在模$7$意义下的逆元，$3\times 5=15\equiv 1(\mathrm{mod}7)$。

在模意义下，我们记上文中的$b$为$a^{-1}$（即$a$的模倒数）

对于求逆元，有一种快速的方法（费马小定理），但我更推荐枚举，毕竟你们不是计算机。

回到正题

---

中国剩余定理可以用来求解形如以下形式的线性同余方程（其中$n_1,n_2,\dots ,n_k$两两互质）：
$$\{\begin{array}{l}x\equiv a_1(\mathrm{mod}{m}_1)\\ x\equiv a_2(\mathrm{mod}{m}_2)\\ ⋮\\ x\equiv a_k(\mathrm{mod}{m}_k)\end{array}$$

其中，$x\equiv a_i(\mathrm{mod}{m}_i)$表示$a_i$是$x÷m_i$的余数，例如$5\equiv 1(\mathrm{mod}2)$。

开始解答

---

欧买噶的，你竟然学会同余线性方程组了！超越了LLL！

那么，来求$x$吧：

• 首先，计算${\prod }_{i=1}^k{m}_i$，即所有$n_i$的乘积，记为$m$（不带下标）
• 接着，对于第$i$个方程：
  1. 计算$b_i=\frac{m}{m_i}$，即除$n_i$之外所有$n_j$的乘积
  2. 计算$b_i$在模$m_i$意义下的逆元（不记得翻回去看），记为$b_i^{-1}$
  3. 计算$c_i=b_i\times b_i^{-1}$，此时不对$m_i$取模
• 最后，该线性方程在模$n$意义下的唯一解为：$x={\sum }_{i=1}^k{a}_i\times c_i(\mathrm{mod}{m}_i)$，即$x$等于所有$a_i\times c_i$的和。

回到题目，提取题目中的同余方程组为：
$$\{\begin{array}{l}x\equiv 2(\mathrm{mod}3)\\ x\equiv 3(\mathrm{mod}5)\\ x\equiv 3(\mathrm{mod}7)\end{array}$$

易得，$n=105$

以$x\equiv 2(\mathrm{mod}3)$为例，我们计算一下：

$b=\frac{n}{3}=35$。

此时，$1\times 35\equiv 2(\mathrm{mod}3),2\times 35\equiv 1(\mathrm{mod}3)$，即$b^{-1}=2$，则$c=70$

以此类推，我们算得，答案为$2\times 35+1\times 21+1\times 15=233\equiv 23(\mathrm{mod}105)$，所以答案最小为$23$。

可以撒花了。

证明

---

这里空间还蛮大的，写一写证明吧！

正确性保证

---

由式子$x\equiv {\sum }_{i=1}^k{a}_i\times c_i(\mathrm{mod}m)$，得：
$$\begin{array}{rlr}x& \equiv \sum _{i=1}^k{a}_i\times c_i& (\mathrm{mod}m)\\ & \equiv \sum _{i=1}^k{a}_i\times b_i\times (b_i^{-1}(\mathrm{mod}{m}_i))& (\mathrm{mod}m)\\ & \equiv \sum _{i=1}^k{a}_i& (\mathrm{mod}m)\end{array}$$
这样就满足对于每一个$i$其对应的方程，$x$都是成立的。

最优性保证（相当于正确性保证）

---

口胡一下吧，似乎挺严格：

首先，模意义下的答案具有唯一性：

因为如果存在$x\ne y$，则必然存在$m_i$满足$x,y$不同余。

又因为$x<m$（余数一定小于除数），

所以$x$一定是满足所有条件的方程组当中最小的。

完结，撒花★,°:.☆(￣▽￣)/$:.°★ 。