最后更新: 2025-10-17 09:27 查看: 53 次纠错评论(0) 课件开VIP

中国剩余定理与格朗日插值多项式

## 中国剩余定理
在有理整数环中，我们研讨了 $\mathbb{Z}$ 模其理想 $I$ 的商环 $\mathbb{Z} / I$ ，它大致相当于线性空间的商空间．在 $K[x]$ 内，我们同样应当研究 $K[x]$模它的一个理想 $I$ 的商环。但对这个课题的研讨，我们将留到抽象代数课中从更一般的角度来阐述，这里将限于讨论一些基本概念．

设 $I$ 是 $K[x]$ 的一个理想，如果 $f(x), g(x) \in K[x]$ ，且 $g(x)- f(x) \in I$ ，则称 $g(x)$ 与 $f(x)$ **模 $I$ 同余**，并记做 $g(x) \equiv f(x) (\bmod I)$ ．现设 $I$ 为非平凡理想，则 $I=(m(x))$ ，其中 $m(x) \in K[x]$且满足 $\operatorname{deg} m(x) \geqslant 1$ ．这时

$$
g(x) \equiv f(x)(\bmod I) \Longleftrightarrow m(x) \mid(g(x)-f(x)) .
$$

所以我们写 $g(x) \equiv f(x)(\bmod m(x))$ ，称 **$g(x)$ 与 $f(x)$ 模 $m(x)$ 同余**．和 $\mathbb{Z}$ 内的同余式一样，同余关系也是 $K[x]$ 内的一个等价关系，

具有如下性质：
$1)$ 反身性：$f(x) \equiv f(x)(\bmod m(x))$ ；
$2)$ 对称性：若 $g(x) \equiv f(x)(\bmod m(x))$ ，则

$$
f(x) \equiv g(x)(\bmod m(x)) ;
$$

$3)$ 传递性：若 $f(x) \equiv g(x)(\bmod m(x)), g(x) \equiv h(x) (\bmod m(x))$ ，则 $f(x) \equiv h(x)(\bmod m(x))$ 。

因此，$K[x]$ 内的多项式也按模 $m(x)$ 同余划分为互不相交的同余类，而 $K[x]$ 则是这些同余类的并集．

我们有如下性质：
$1)$ 若 $f_1(x) \equiv g_1(x)(\bmod m(x)), f_2(x) \equiv g_2(x)(\bmod m(x))$ ，则

$$
\begin{aligned}
& f_1(x) \pm f_2(x) \equiv\left(g_1(x) \pm g_2(x)\right)(\bmod m(x)), \\
& f_1(x) f_2(x) \equiv g_1(x) g_2(x)(\bmod m(x)) .
\end{aligned}
$$

2）若 $f(x) h(x) \equiv g(x) h(x)(\bmod m(x))$ ，又 $(h(x), m(x))=1$ ，则 $f(x) \equiv g(x)(\bmod m(x))$ 。

性质 1）请读者自行证明．我们证明性质 2）：按定义，有 $m(x) \mid (h(x) f(x)-h(x) g(x))$ ，于是 $m \mid h(f-g)$ ，但 $(m, h)=1$ ，按照命题 1.3 的推论 $3, m \mid(f-g)$ ，即 $f \equiv g(\bmod m)$ ．

**引理** 设 $q_1(x), \cdots, q_r(x)$ 是 $K[x]$ 内一组两两互素且次数 $\geqslant 1$的多项式，则对任一 $i(1 \leqslant i \leqslant r)$ ，存在多项式 $h_i(x) \in K[x]$ ，使

$$
h_i(x) \equiv 1\left(\bmod q_i(x)\right), \quad h_i(x) \equiv 0\left(\bmod q_j(x)\right) \quad(j \neq i) .
$$

证 对任一 $j \neq i$ ，有 $\left(q_i(x), q_j(x)\right)=1$ ，于是存在 $u_j(x), v_j(x) \in K[x]$ ，使 $u_j(x) q_i(x)+v_j(x) q_j(x)=1$ ．令

$$
h_i(x)=\prod_{\substack{j=1 \\ j \neq i}}^r v_j \cdot q_j .
$$

我们有 $h_i(x) \equiv 0\left(\bmod q_j(x)\right)(j \neq i)$ ，而且

$$
h_i(x)=\prod_{j \neq i}\left(1-u_j q_i\right)=1+q_i u \equiv 1\left(\bmod q_i\right),
$$

其中 $u$ 为展开式中提出公因式 $q_i$（除第一项 1 之外）后所剩的多项式。

## 中国剩余定理
**定理1.2（中国剩余定理）** 设 $q_1(x), \cdots, q_r(x)$ 为 $K[x]$ 内两两

互 素且次数 $\geqslant 1$ 的多项式，任给 $f_1(x), \cdots, f_r(x) \in K[x]$ ，必存在 $f(x) \in K[x]$ ，使

$$
f(x) \equiv f_i(x)\left(\bmod q_i(x)\right) \quad(i=1,2, \cdots, r) .
$$

证 根据引理，对每个 $i(1 \leqslant i \leqslant r)$ ，存在 $h_i(x)$ ，满足

$$
h_i(x) \equiv 1\left(\bmod q_i(x)\right), \quad h_i(x) \equiv 0\left(\bmod q_j(x)\right) \quad(j \neq i)
$$

令 $f(x)=\sum_{k=1}^r f_k(x) h_k(x)$ ，则对每个 $i(1 \leqslant i \leqslant r)$ ，有

$$
f_i(x) h_i(x) \equiv f_i(x)\left(\bmod q_i(x)\right)
$$

而 当 $k \neq i$ 时 $f_k(x) h_k(x) \equiv 0\left(\bmod q_i(x)\right)$ ，于是 $f_i(x) h_i(x)=f_i(x) +m_i(x) q_i(x), f_k(x) h_k(x)=m_k(x) q_i(x)$ ，这里 $m_i(x), m_k(x) \in K[x]$ ．由此得

$$
\begin{aligned}
f(x) & =\sum_{k \neq i} f_k(x) h_k(x)+f_i(x) h_i(x) \\
& =\sum_{k \neq i} m_k(x) q_i(x)+f_i(x)+m_i(x) q_i(x) \\
& =f_i(x)+\left(\sum_{k=1}^r m_k(x)\right) q_i(x)
\end{aligned}
$$

这表明

$$
f(x) \equiv f_i(x)\left(\bmod q_i(x)\right) \quad(i=1,2, \cdots, r) .
$$
下面来给出中国剩余定理的一个简单的应用．

`例`设 $a_1, a_2, \cdots, a_r$ 是 $K$ 内一组两两不相等的元素，令 $q_i(x)= x-a_i$ ，这是 $K[x]$ 内一组互不相同的不可约多项式，显然两两互素．在 $K$ 内任给 $r$ 个数 $b_1, \cdots, b_r$ ，令 $f_i(x)=b_i$ 。按照中国剩余定理，存在 $f(x) \in K[x]$ ，使 $f(x) \equiv b_i\left(\bmod \left(x-a_i\right)\right)$ ，即

$$
f(x)=b_i+q_i(x)\left(x-a_i\right) \quad(i=1,2, \cdots, r) .
$$

令 $x=a_i$ 代入，即得 $f\left(a_i\right)=b_i \quad(i=1,2, \cdots, r)$ 。从中国剩余定理的证明过程，我们可把 $f(x)$ 的具体表达式找出来：

1）求 $h_i(x)$ 。按引理的证明，因为我们有

$$
\frac{1}{a_j-a_i}\left(x-a_i\right)+\frac{1}{a_i-a_j}\left(x-a_j\right)=1,
$$

故应取

$$
h_i(x)=\prod_{j \neq i} \frac{x-a_j}{a_i-a_j}
$$
$$
=\frac{\left(x-a_1\right) \cdots\left(x-a_{i-1}\right)\left(x-a_{i+1}\right) \cdots\left(x-a_r\right)}{\left(a_i-a_1\right) \cdots\left(a_i-a_{i-1}\right)\left(a_i-a_{i+1}\right) \cdots\left(a_i-a_r\right)} .
$$

2）令

$$
f(x)=\sum_{k=1}^r b_k h_k(x)
$$

显然， $\operatorname{deg} h_i(x)=r-1$ ，故 $\operatorname{deg} f(x) \leqslant r-1$ ．由（2）式所定义的 $f(x)$ ，其次数不超过 $r-1$ ，而且在 $r$ 个不同点 $a_1, \cdots, a_r$ 处取预先任意指定的值 $b_1, \cdots, b_r$ ．这个多项式称为拉**格朗日插值多项式**．读者借助线性方程组理论很容易证明，（2）式是满足上述条件的唯一多项式。

作为中国剩余定理的一个重要应用，我们来证明关于线性变换的一个著名的分解定理．

## 中国剩余定理的解读

想象一下，你是古代的大将军韩信，你需要清点你手下一共有多少士兵。人数太多，直接数容易乱。你想了一个巧妙的办法：

1.  你让士兵们**每3人一排**站好，发现最后多出了**2**个士兵（无法排成一排）。
2.  接着，你让他们**每5人一排**站好，发现最后多出了**3**个士兵。
3.  最后，你让他们**每7人一排**站好，发现最后多出了**2**个士兵。

现在问题来了：在不直接一个一个数的情况下，你怎么能算出至少有多少士兵呢？

这个“分苹果”的问题，就是中国剩余定理要解决的核心问题。

---

### 中国剩余定理的核心思想

中国剩余定理说的是这样一件事：

> 如果我们知道一个数（士兵总数）**除以几个两两互质的数字（3，5，7）** 后得到的**余数（2，3，2）**，那么我们就可以**唯一地确定**这个数在一定范围内是多少。

**“互质”是什么意思？**
就是这几个数之间没有共同的因数（除了1）。比如3、5、7，它们谁也不能整除谁。

**为什么它能工作？**
我们可以把这个问题想象成**在一个多维的“余数空间”里定位一个点**。

*   “除以3余2”就像是在说：这个数在一条以3为周期的数轴上，它位于“2”这个位置。
*   “除以5余3”像是在另一条以5为周期的数轴上，它位于“3”这个位置。
*   “除以7余2”像是在第三条以7为周期的数轴上，它位于“2”这个位置。

中国剩余定理保证，因为3、5、7是互质的，它们的组合周期（3×5×7=105）足够大，以至于在0到104这个范围内，**有且只有一个数**能同时满足在这三条数轴上的特定位置。

---

### 让我们来找出这个数

我们可以用一种“拼凑”的思路来找到答案：

1.  **找一个数，满足“除以3余2”**：
    *   首先，找一个数是5和7的公倍数，也就是35的倍数，同时它除以3余1。这个数是70 (70÷3=23余1)。
    *   但是我们需要余数是2，所以把70乘以2，得到 **140**。(140 ÷ 3 = 46 ... **余2**)

2.  **找一个数，满足“除以5余3”**：
    *   找一个数是3和7的公倍数，也就是21的倍数，同时它除以5余1。这个数是21 (21÷5=4余1)。
    *   但是我们需要余数是3，所以把21乘以3，得到 **63**。(63 ÷ 5 = 12 ... **余3**)

3.  **找一个数，满足“除以7余2”**：
    *   找一个数是3和5的公倍数，也就是15的倍数，同时它除以7余1。这个数是15 (15÷7=2余1)。
    *   但是我们需要余数是2，所以把15乘以2，得到 **30**。(30 ÷ 7 = 4 ... **余2**)

4.  **把这三个结果加起来**：
    *   140 + 63 + 30 = **233**

5.  **找到最小的那个解**：
    *   233这个数肯定满足我们的条件，但它可能不是最小的。因为3、5、7的最小公倍数是105，所以我们从233里减去105的倍数。
    *   233 - 2×105 = 233 - 210 = **23**

所以，**士兵的总数至少是23人**。

**验证一下：**
*   23 ÷ 3 = 7 ... **余2** ✅
*   23 ÷ 5 = 4 ... **余3** ✅
*   23 ÷ 7 = 3 ... **余2** ✅

完全正确！
 
**中国剩余定理的通俗解释就是：**

> 当我们要找一个未知数时，如果我们知道它被几个“互质的除数”除后留下的“余数”，那么我们就可以像**用多个坐标锁定一个位置**一样，把这个数准确地找出来。

**它在现实世界有什么用？**

*   **密码学**：RSA等现代加密算法大量使用模运算，中国剩余定理可以大大加快解密和签名的速度。
*   **计算机科学**：处理大整数计算时，可以把一个大数用它对几个小数的余数来表示，分别计算后再用中国剩余定理还原结果，这样可以并行计算，提高效率。
*   **日历计算**：计算某一天是星期几，本质上也是一个求余数的问题。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：重因式

下一篇： Jordan－Chevally 分解定理

本文对您是否有用？有用 (0) 无用 (0)