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

Euler 函数、费马小定理与剩余定理

## 1．Euler 函数
**定义** 设 $m$ 是一正整数．如果 $a \in \mathbb{Z},(a, m)=1$ ，则 $a+(m)$ 称为**与 $m$ 互素的剩余类**。在全部模 $m$ 剩余类中，与 $m$ 互素的剩余类的数目记做 $\varphi(m)$ ，称为 **Euler函数**．

> **欧拉函数 $\varphi(n) $ 表示 小于等于  n  的正整数中，与   n  互质的数的个数,详见 [此处](https://kb.kmath.cn/kbase/detail.aspx?id=795)**。

Euler 函数有许多重要的应用．我们先来指出一个简单的事实．设
$$
r_1+(m), r_2+(m), \cdots, r_t+(m) \quad(t=\varphi(m))
$$

是全部互不相同的与 $m$ 互素的剩余类，又设 $k \in \mathbb{Z},(k, m)=1$ ，则

$$
k r_1+(m), k r_2+(m), \cdots, k r_t+(m)
$$

也是全部互不相同的与 $m$ 互素的剩余类。其所以如此，是因为 $\left(r_i, m\right)=1$ ，故 $\left(k r_i, m\right)=1$ ，即 $k r_i+(m)$ 为与 $m$ 互素的剩余类。又若 $k r_i+(m)=k r_j+(m)(i \neq j)$ ，则 $k r_i \equiv k r_j(\bmod m)$ ，由命题2．1，有 $r_i \equiv r_j(\bmod m)$ ，从而 $r_i+(m)=r_j+(m)$ ，与假设矛盾．

**命题2.2（Euler定理）** 设 $k$ 是与正整数 $m$ 互素的整数，则

$$
k^{\varphi(m)} \equiv 1(\bmod m)
$$

证 设全部互不相同的与 $m$ 互素的剩余类是

$$
r_1+(m), r_2+(m), \cdots, r_t+(m), \quad t=\varphi(m),
$$

则

$$
k r_1+(m), k r_2+(m), \cdots, k r_t+(m)
$$

与上述 $t$ 个剩余类仅是排列次序不同而已，所以把它们连乘起来应当相等，因而有
$$
\begin{aligned}
\prod_{i=1}^t r_i+(m) & =\prod_{i=1}^t\left(r_i+(m)\right)=\prod_{i=1}^t\left(k r_i+(m)\right) \\
& =\prod_{i=1}^t k r_i+(m)=k^t \prod_{i=1}^t r_i+(m)
\end{aligned}
$$

于是

$$
k^t \prod_{i=1}^t r_i \equiv \prod_{i=1}^t r_i(\bmod m)
$$

因 $\left(r_i, m\right)=1$ ，故 $\left(r_1 r_2 \cdots r_t, m\right)=1$ ．按命题 2.1 的（ii），有

$$
k^t \equiv 1(\bmod m)
$$

现 $t=\varphi(m)$ ，故命题得证．

## Fermat 费马小定理
**推论（Fermat 小定理）** 设 $p$ 为素数，若 $p$ 不整除整数 $k$ ，则 $k^{p-1} \equiv 1(\bmod p)$.

证 模 $p$ 的 $p$ 个剩余类，除 $0+(p)$ 外，均为与 $p$ 互素的剩余类，即 $\varphi(p)=p-1$ ，现在有 $(p, k)=1$ ，由 Euler 定理即知本命题成立。

### Euler函数表达式
下面来给出 Euler函数 $\varphi(m)$ 的表达式。

**命题2.3** 设 $m_1, m_2$ 是两个正整数，$\left(m_1, m_2\right)=1$ ．则
$$
\begin{gathered}
r_1 m_2+r_2 m_1+\left(m_1 m_2\right) \\
\left(r_1=0,1,2, \cdots, m_1-1 ; r_2=0,1,2, \cdots, m_2-1\right)
\end{gathered}
$$

为全部互不相同的模 $m_1 m_2$ 的剩余类。

证 所给剩余类有 $m_1 m_2$ 个，只要证两两不同．若

$$
r_1 m_2+r_2 m_1+\left(m_1 m_2\right)=r_1^{\prime} m_2+r_2^{\prime} m_1+\left(m_1 m_2\right),
$$

其中 $0 \leqslant r_1, r_1^{\prime}<m_1, 0 \leqslant r_2, r_2^{\prime}<m_2$ ．此时有

$$
r_1 m_2+r_2 m_1 \equiv r_1^{\prime} m_2+r_2^{\prime} m_1 \quad\left(\bmod m_1 m_2\right),
$$

从而

$$
r_1 m_2+r_2 m_1 \equiv r_1^{\prime} m_2+r_2^{\prime} m_1 \quad\left(\bmod m_1\right) .
$$

由上式立知 $r_1 m_2 \equiv r_1^{\prime} m_2\left(\bmod m_1\right)$ ，因 $\left(m_1, m_2\right)=1$ ，按命题 2.1 的 （ii），$r_1 \equiv r_1^{\prime}\left(\bmod m_1\right)$ ，于是 $r_1=r_1^{\prime}$ 。同理 $r_2=r_2^{\prime}$ 。

**命题2.4** 设 $m_1, m_2$ 是互素正整数，则

$$
\varphi\left(m_1 m_2\right)=\varphi\left(m_1\right) \varphi\left(m_2\right) .
$$

证 设与 $m_1$ 互素的剩余类全体列举如下：

$$
r_1+\left(m_1\right), r_2+\left(m_1\right), \cdots, r_s+\left(m_1\right), \quad s=\varphi\left(m_1\right) .
$$

又设与 $m_2$ 互素的剩余类全体列举如下：

$$
l_1+\left(m_2\right), l_2+\left(m_2\right), \cdots, l_t+\left(m_2\right), \quad t=\varphi\left(m_2\right) .
$$

来证
$$
\begin{gathered}
r_i m_2+l_j m_1+\left(m_1 m_2\right) \\
(i=1,2, \cdots, s ; j=1,2, \cdots, t)
\end{gathered}
$$

恰为与 $m_1 m_2$ 互素的剩余类的全体。
（i）先证 $\left(r_i m_2+l_j m_1, m_1 m_2\right)=d=1$ ．用反证法．若 $d \neq 1$ ，设 $d$ 有一素数因子 $p$ ，则 $p \mid m_1 m_2$ ，因 $\left(m_1, m_2\right)=1$ ，由命题 $1.4, p \mid m_1$ 或 $p \mid m_2$ ．若 $p \mid m_1$ ，又因 $p \mid\left(r_i m_2+l_j m_1\right)$ ，故 $p \mid r_i m_2$ ，又 $\left(p, m_2\right)=1$ ，因而 $p \mid r_i$ ，于是 $r_i$ 与 $m_1$ 不互素，矛盾．同样，如假定 $p \mid m_2$ 也导出矛盾．这表明必有 $d=1$ ．于是 $r_i m_2+l_j m_1+\left(m_1 m_2\right)$ 是与 $m_1 m_2$ 互素的剩余类．
（ii）再证若 $r m_2+l m_1+\left(m_1 m_2\right)$ 为与 $m_1 m_2$ 互素的剩余类，必定 $\left(r, m_1\right)=1,\left(l, m_2\right)=1$ 。用反证法。设 $r, m_1$ 有一公共素数因子 $p$ ，由 $p|r, p| m_1$ 知 $p \mid\left(r m_2+l m_1\right)$ ，又 $p \mid m_1 m_2$ ，与 $\left(r m_2+l m_1, m_1 m_2\right)=1$ 之设矛盾．同理 $\left(l, m_2\right)=1$ ．
（iii）在命题 2.3 中已排出全部模 $m_1 m_2$ 的剩余类，其中与 $m_1 m_2$互素的恰为式（1）中列举的 $s t$ 个，于是

$$
\varphi\left(m_1 m_2\right)=s t=\varphi\left(m_1\right) \varphi\left(m_2\right)
$$

**命题2.5** 设正整数 $n=p_1^e p_2^e \cdots p_k^e$ 为 $n$ 的素因子标准分解式，则

$$
\varphi(n)=n\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right) \cdots\left(1-\frac{1}{p_k}\right) .
$$

证 按命题2．4，有

$$
\varphi(n)=\varphi\left(p_1^{e_1}\right) \varphi\left(p_2^{e_2}\right) \cdots \varphi\left(p_k^{e_k}\right) .
$$

对素数 $p$ ，应有 $\varphi\left(p^e\right)=p^e-p^{e-1}=p^e\left(1-\frac{1}{p}\right)$ 。这是因为模 $p^e$ 的剩余类的全体是

$$
0+\left(p^e\right), 1+\left(p^e\right), \cdots, p^e-1+\left(p^e\right) .
$$

若 $a+\left(p^e\right)$ 与 $p^e$ 不互素，则 $p \mid a$ ，而 $0 \leqslant a<p^e$ ．显然 $a=q p$ ，其中

$$
q=0,1,2, \cdots,\left(p^{e-1}-1\right)
$$

共 $p^{e-1}$ 个，故 $\varphi\left(p^e\right)=p^e-p^{e-1}$ 。
最后，我们指出：由于 $(0,1)=1$ ，故 $\varphi(1)=1$ ．

## 中国剩余定理
现在我们介绍一个在代数学与数论中起重要作用的定理。
**定理2.1 （中国剩余定理）** 设 $m_1, m_2, \cdots, m_k$ 是 $k$ 个两两互素的正整数．任给 $k$ 个整数 $a_1, a_2, \cdots, a_k$ ，必存在整数 $x$ ，使

$$
x \equiv a_i\left(\bmod m_i\right) \quad(i=1,2, \cdots, k) .
$$

证 定理分两步证明．
（i）对一固定的 $i$ 。当 $j \neq i$ 时，$\left(m_i, m_j\right)=1$ ，按命题1．3的推论 2 ，有 $u_j, v_j \in \mathbb{Z}$ ，使 $u_j m_i+v_j m_j=1$ 。令

$$
w_i=\prod_{\substack{j=1 \\ j \neq i}}^k v_j m_j \equiv 0\left(\bmod m_l\right) \quad(l \neq i)
$$

另一方面有

$$
w_i=\prod_{\substack{j=1 \\ j \neq i}}^k\left(1-u_j m_i\right)=1+q_i m_i
$$
（ii）利用上面得到的 $w_1, w_2, \cdots, w_k$ 构作整数

$$
x=\sum_{j=1}^k a_j w_j .
$$

当 $j \neq i$ 时，$m_i \mid w_j$ ，即 $w_j=q_j m_i$ ，而 $w_i=1+q_i m_i$ ，代入上式得

$$
x=\sum_{j \neq i} a_j q_j m_i+a_i\left(1+q_i m_i\right) \equiv a_i\left(\bmod m_i\right) .
$$

定理得证．

## 本章解读

### 欧拉函数
#### 1. 核心思想：数“朋友”的个数

我们固定一个正整数 $ n $，比如 $ n = 8 $。

考虑从 $ 1, 2, 3, ..., n $ 这些数字中，有多少个与 $ n $ 是“互质”的（互质的意思是最大公约数为 1，即两个数没有大于 1 的公共因子）。

这个**互质的数的个数**，就是欧拉函数，记作 $ \varphi(n) $。

#### 2. 生活化比喻：**找队友**

假设有 $ n $ 个人站成一圈，要玩一个“手拉手”游戏，但要求：**只有号码互质的人才能安全拉手**。

欧拉函数 $\varphi(n)$ 就是问：**号码 1 号人物，有多少个可以安全拉手的队友**（不包括自己，范围是 1 到 n）？

其实更准确地说，是“在 1 到 n 中，有多少个数与 n 互质”。

### 3. 例子

**例 1：$ n = 8 $**
1 到 8 的数字：1, 2, 3, 4, 5, 6, 7, 8  
与 8 互质（没有公共因子大于 1）：
- 1：gcd(1,8)=1 ✅
- 2：gcd(2,8)=2 ❌
- 3：gcd(3,8)=1 ✅
- 4：gcd(4,8)=4 ❌
- 5：gcd(5,8)=1 ✅
- 6：gcd(6,8)=2 ❌
- 7：gcd(7,8)=1 ✅
- 8：gcd(8,8)=8 ❌

互质的有：1, 3, 5, 7  
一共 4 个。

所以 **$\varphi(8) = 4$**。

**例 2：$ n = 9 $**
1 到 9：1, 2, 3, 4, 5, 6, 7, 8, 9  
与 9 互质（不能有因子 3）：
- 去掉 3, 6, 9（都有公因子 3）  
剩下：1, 2, 4, 5, 7, 8  
一共 6 个。

所以 **$\varphi(9) = 6$**。

**例 3：$ n = 7 $（质数）**
质数和所有比它小的正整数都互质。  
1 到 7 中与 7 互质的有：1, 2, 3, 4, 5, 6  
一共 6 个。

**质数 $ p $ 的欧拉函数：$\varphi(p) = p-1$**。

---

#### 4. 计算方法（知道即可）

- 如果 $ n = p^k $（质数的幂），则 $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p-1)$。  
  例：$ \varphi(8) = \varphi(2^3) = 2^3 - 2^2 = 8 - 4 = 4$。

- 一般地，如果 $ n = p_1^{k_1} p_2^{k_2} \dots $，则  
 $$
  \varphi(n) = n \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \dots
$$
  例：$ n = 10 = 2 \times 5$  
  $\varphi(10) = 10 \times (1 - \frac12) \times (1 - \frac15) = 10 \times \frac12 \times \frac45 = 4$。

一句话 
>**欧拉函数 $\varphi(n)$ 就是计算在 1 到 n 的正整数中，与 n 互质的数的个数。**

### 费马小定理
 欧拉定理：如果 $\gcd(a, n) = 1$，则  
 $$
  a^{\varphi(n)} \equiv 1 \pmod{n}
$$
  这是费马小定理的推广。

#### 1. 一句话核心

**如果一个整数 $a$ 不是质数 $p$ 的倍数，那么把 $a$ 连乘 $p-1$ 次以后，减去 1，结果一定能被 $p$ 整除。**

用数学符号写：
$$
a^{p-1} \equiv 1 \pmod{p} \quad (\text{当 } p \nmid a)
$$

---

#### 2. 直观例子

取质数 $p = 5$，选一个不是 5 的倍数的数，比如 $a = 2$。

计算：
$$
2^{5-1} = 2^4 = 16
$$
16 除以 5 余数是 1，所以：
$$
16 \equiv 1 \pmod{5}
$$
正确。

再试 $a = 3$：
$$
3^{4} = 81
$$
81 除以 5 余 1，也成立。

---

#### 3. 生活化比喻：**颜色循环**

假设我们有 $p$ 种颜色（$p$ 是质数），给一个转盘上色，每次转动固定角度对应一种颜色变化规则。

定理说：**从任意非零颜色出发，连续变换 $p-1$ 次后，一定会回到起始颜色**。

---

#### 4. 更具体的比喻：**时钟算术（质数时钟）**

想象一个 $p$ 小时的时钟（比如 $p=5$ 点时钟）。

- 从 0 点到 4 点（共 5 个点）。
- 你选一个点数 $a$（不是 0 点），比如 2 点。
- 你每次向前跳 $a$ 小时（乘法相当于连续加）。
- 跳 $p-1=4$ 次后（即 $a^{p-1}$ 的位置），你一定回到 1 点位置（即 1 mod p）。

为什么？因为质数时钟的乘法会遍历所有非零点，最后回到起点。
 
#### 5. 注意条件

1. $p$ 必须是**质数**。
2. $a$ 与 $p$ 互质（即 $a$ 不是 $p$ 的倍数）。
3. 结论是在模 $p$ 意义下成立的，即考虑余数。

一句话总结

> **费马小定理说的是：在质数模的世界里，任何不是它倍数的数，其（质数-1）次幂模质数余 1。**

### 中国剩余定理
想象一个数被几把不同的“模数锁”锁住，每把锁只告诉我们这个数除以某个数的余数。中国剩余定理说：只要这些锁的模数两两互质，我就可以唯一确定这个数（在它们乘积范围内）。

#### 1. 生活化比喻：**找共享密码**

假设有三个朋友约好确定一个共同密码（在 0 到 104 之间）：
- A 说：密码除以 3 余 2
- B 说：密码除以 5 余 3
- C 说：密码除以 7 余 2

中国剩余定理保证：**在 0 到 $3×5×7-1=104$ 之间，有且只有一个数满足这三个条件**。
这里算出是 **23**。检验：

- 23 ÷ 3 = 7 余 2 ✅
- 23 ÷ 5 = 4 余 3 ✅
- 23 ÷ 7 = 3 余 2 ✅

#### 2. 为什么叫“中国”？

因为最早出现在中国南北朝时期的《孙子算经》（公元4-5世纪），比欧洲早1000多年。

#### 3. 直观理解：**多维坐标**

把每个模数 $m_i$想象成一个坐标轴的长度：
- 模 3 的余数：就像在一条 3 个单位长的循环线段上的位置（0,1,2）
- 模 5 的余数：在一条 5 个单位长的循环线段上的位置
- 模 7 的余数：在一条 7 个单位长的循环线段上的位置

因为 3,5,7 互质，它们的乘积 $105$ 就像一个“三维周期空间”的大小。在这个空间里，每个点的“坐标”（余数）都是唯一的。

####  重要提醒

**必须两两互质**，否则不一定有解，即使有解也可能不唯一。

例：除以 4 余 1，除以 6 余 3 → 有无穷多解（9, 21, 33, …），因为 4 和 6 不互质。
 
总结

> **中国剩余定理说的是：用多个两两互质的除数及其余数，可以唯一确定一个数（在它们乘积范围内）。就像用经纬度确定地球上的位置一样，每个条件缩小范围，最后锁定目标。**

其他版本
【初中数学】费马小定理与欧拉定理

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：同余式与剩余类

下一篇：模m的剩余类环

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