最后更新: 2025-10-20 09:56 查看: 440 次纠错评论(0) 课件开VIP

剩余系与欧拉函数

## 剩余类
在同余式的运算中，两个同余数起的作用是一样的，可以把互相同余的这些数归于一类．由此引进剩余类的概念．在上一节已经接受过了，这里简单回顾一下。

**定义1** 设 $m$ 为正整数，所有对 $m$ 同余的整数所组成的集合称为模 $m$ 的一个剩余类．由定义，全体整数对模 $m$ 可分为 $m$ 个互不相交的剩余类 $K_0, K_1, \cdots, K_{m-1}$ ，其中

$$
K_r=\{q m+r\}, q=0, \pm 1, \pm 2, \cdots, 0 \leqslant r < m .
$$

`例` 
模 5 的剩余类： 相当于每个整数m除以5的余数。

- $[0] = \{\dots, -10, -5, 0, 5, 10, \dots\}$
- $[1] = \{\dots, -9, -4, 1, 6, 11, \dots\}$
- $[2] = \{\dots, -8, -3, 2, 7, 12, \dots\}$
- $[3] = \{\dots, -7, -2, 3, 8, 13, \dots\}$
- $[4] = \{\dots, -6, -1, 4, 9, 14, \dots\}$

把上面结果用集合表示出来就是
对模 5，其到余类有如下五个：

$$
\begin{aligned}
& K_0=\{5 q \mid q \in Z \}, \\
& K_1=\{5 q+1 \mid q \in Z \}  \\
& K_2=\{5 q+2 \mid q \in Z \} \\
& K_3=\{5 q+3 \mid q \in Z \} \\
& K_4=\{5 q+4 \mid q \in Z \} .
\end{aligned}
$$

`例` 列出 $Z _7$ 的乘法表
解：
$$
\begin{array}{l|lllllll} 
& 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
1 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\
2 & 0 & 2 & 4 & 6 & 1 & 3 & 5 \\
3 & 0 & 3 & 6 & 2 & 5 & 1 & 4 \\
4 & 0 & 4 & 1 & 5 & 2 & 6 & 3 \\
5 & 0 & 5 & 3 & 1 & 6 & 4 & 2 \\
6 & 0 & 6 & 5 & 4 & 3 & 2 & 1
\end{array}
$$

表中数字 $0,1,2, \cdots, 6$ 分别代表剩余数类 $\overline{0}, \overline{1}, \overline{2}, \cdots, \overline{6}$ 。这里的乘法与数的乘法是不同的。例如表中第四行第五列表示 $\overline{3} \cdot \overline{4}=\overline{5}$ ，第五行与第六列表示 $\overline{4} \cdot \overline{5}=\overline{6}$ 。

## 剩余系

为了在下一节能够证明数论中一个著名的定理一 欧拉定理，我们需要有关到剩余系和欧拉的数的知识

**定义1** 设 $\varphi(1)=1$ ，当 $n>1, \varphi(n)$ 表示 $1,2, \cdots, n-1$ 中与 $n$ 互素的数的个数，称 $\varphi(n)$ 为欧拉函数．

> **欧拉函数 $ \varphi(n) $ 表示 小于等于 $ n $ 的正整数中，与 $ n $ 互质的数的个数**。

这里“互质”的意思是：两个数的最大公约数（GCD）为 1。

用数学符号表示：
$$
\varphi(n) = \#\{ k \in \mathbb{Z}^+ \mid 1 \le k \le n \ \text{且} \ \gcd(k, n) = 1 \}
$$
其中 $\#$ 表示集合中元素的个数。

我们通过几个例子来直观理解：

`例`$ \varphi(1) = 1 $ 
  因为 1 与 1 互质（$\gcd(1,1)=1$），并且只有 1 这个数。

`例`$ \varphi(5) = 4 $  
  在 1, 2, 3, 4, 5 中，除了 5 与 5 不互质（gcd=5），其他 1,2,3,4 都与 5 互质。所以有 4 个数。

`例`$ \varphi(6) = 2 $  
  检查 1 到 6：  
  - $\gcd(1,6)=1$ ✓  
  - $\gcd(2,6)=2$ ✗  
  - $\gcd(3,6)=3$ ✗  
  - $\gcd(4,6)=2$ ✗  
  - $\gcd(5,6)=1$ ✓  
  - $\gcd(6,6)=6$ ✗  
  所以只有 1 和 5 两个数，因此 $\varphi(6) = 2$。

`例`$ \varphi(9) = 6 $ 
  与 9 互质的数：1, 2, 4, 5, 7, 8（共 6 个）。不与 9 互质的是 3, 6, 9。
  
例如，当 $p$ 为素数时，由定义即知 $\varphi(p)=p-1$ ．又如 $\varphi(6)=2, \varphi(8)=4, \varphi(15)=8$ ．

**定义2** 若模 $m$ 的某个剩余类中的数与 $m$ 是互素的，则称此剩余类为模 $m$ 的互素剩余类  ．

> 在模 $m$ 的一个剩余类中，只要有一个数与 $m$ 互素。则此剩余类中所有的数都与 $m$互素。

**定义3** 从模 $m$ 的每个剩余类中各取一个数，得到一个由 $m$ 个数组成的集合，称为模 $m$ 的一个**完全剩余系**。从模 $m$ 的每个互素剩余类中各取一个数，得到一个由 $\varphi(m)$ 个数组成的集合称为模 $m$ 的一个**简化剩余系**．

`例`模 5 的剩余类： 相当于每个整数m除以5的余数。

上面5个剩余数像5个集合，如果任取

$\{0,1,2,3,4\}$是模5的完全剩余系。
$\{-10,-4,2,8,14\}$也是模5的完全剩余系（斜着对角线取的）。
$\{5,6,7,8,9\}$也是模5的完全剩余系

而 $\{1$ ，4\}. \{7,8,9\}是模 5 的简化剩余系．

显然，对固定的模 $m$ ，有无数多个完全剩余系和简化剩余系。任意 $m$ 个整数，只要它们对模 $m$ 两两不同余，这 $m$ 个数就是模 $m$ 的一个完全剩余系。任意 $\varphi(m)$ 个整数，只要它们对模 $m$ 两两不同余并且都和 $m$ 互素，这 $\varphi(m)$ 个数就是模 $m$ 的一个简化剩余系．

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：剩余类及其运算

下一篇：费马小定理与欧拉定理

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