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

费马小定理与欧拉定理

## 费马小定理与欧拉定理

> 在上一节介绍了 [剩余类](https://kb.kmath.cn/kbase/detail.aspx?id=795), 有了剩余类后，就可以引出 费马小定理。

在模 3 的剩余类环中，下列等式是否成立？为什么？
（1）$\left[0^3\right]=[0]$ ；
（2）$\left[1^3\right]=[1]$ ；
（3）$\left[2^3\right]=[2]$ ．

我们发现, 探究中的三个等式都是成立的.
事实上, 我们还可以进一步探究得知, 在模 5 的剩余类环中, 仍然存在这种规律. 即

$$
\begin{aligned}
& {\left[0^5\right]=[0],} \\
& {\left[1^5\right]=[1],} \\
& {\left[2^5\right]=[2],} \\
& {\left[3^5\right]=[3],} \\
& {\left[4^5\right]=[4] .}
\end{aligned}
$$

不难验证, 在模 7 的剩余类环中仍然存在这种规律.

由于 $3,5,7$ 均为素数, 我们大胆地猜想: 当 $m$ 为素数时, 对任意整数 $a$, 总有

$$
\left[a^m\right]=[a] \text {, 或 } a^m \equiv a(\bmod m) .
$$

特别地, 当 $(a, m)=1$ 时, 运用同余意义下的消去律, 可得

$$
a^m \equiv a(\bmod m) \Leftrightarrow a^{m-1} \equiv 1(\bmod m) .
$$

事实上, 这个猜想是正确的. 这就是费马小定理.

> **费马小定理** 设 $m$ 为素数, $a$ 为任意整数,且 $(a, m)=1$, 则 $a^{m-1} \equiv 1(\bmod m)$.

下面我们给出它的证明.
证明: 由 $(a, m)=1$, 可知 $m$ 不是 $a$ 的素因数,又因为 $m$ 不是 $1,2,3, \cdots, m-1$ 的素因数, 所以 $a, 2 a, 3 a, \cdots,(m-1) a$ 均不能被 $m$整除.
又因为 $a, 2 a, 3 a, \cdots,(m-1) a$ 模 $m$ 两两不同余, 所以它们分别属于模 $m$ 的除 $[0]$以外的 $m-1$ 个不同的剩余类中. 由同余的性质 1 可知

$$
\begin{aligned}
& a \times 2 a \times 3 a \times \cdots \times(m-1) a \\
\equiv & 1 \times 2 \times 3 \times \cdots \times(m-1)(\bmod m) .
\end{aligned}
$$

因此 $a^{m-1}(m-1) ! \equiv(m-1) !(\bmod m)$.
又由于 $(m-1)$ ! 不含素因数 $m$, 所以

$$
((m-1) !, m)=1 .
$$

由同余的性质 2 可知

$$
a^{m-1} \equiv 1(\bmod m) .
$$

例如, $a=8, m=5$, 我们知道,

$$
\begin{aligned}
& 8 \times 1 \equiv 3(\bmod 5), 8 \times 2 \equiv 1(\bmod 5), \\
& 8 \times 3 \equiv 4(\bmod 5), 8 \times 4 \equiv 2(\bmod 5) .
\end{aligned}
$$

那么 $8^4 \times 4 ! \equiv 4 !(\bmod 5)$. 而 $(4 !, 5)=1$, 故

$$
8^4 \equiv 1(\bmod 5) \text {. }
$$

### 理解：费马小定理
费马小定理可以理解成一种 **“质数下的循环规律”**。

`例`数的循环
- 你选一个质数，比如 $ p = 5 $。
- 再选一个不是 5 的倍数的数，比如 $ a = 2 $。
- 现在计算 $ a $ 的幂次： $ 2^1 = 2, \ 2^2 = 4, \ 2^3 = 8, \ 2^4 = 16 $。
- 看它们除以 5 的余数：
  - $ 2 \bmod 5 = 2 $
  - $ 4 \bmod 5 = 4 $
  - $ 8 \bmod 5 = 3 $
  - $ 16 \bmod 5 = 1 $  ← 正好是 1！

也就是：$ 2^{5-1} = 16 $ 除以 5 余 1。

`例`想象一个钟表，表盘上有 $ p $ 个格子（$ p $ 是质数），编号 $ 0, 1, 2, \dots, p-1 $。

- 你从 1 号格子出发，每次向前走 $ a $ 步（比如 $ a=2 $）。
- 因为 $ p $ 是质数，并且 $ a $ 不是 $ p $ 的倍数，你**不会**提前回到 1 号格子，必须走完所有 $ p-1 $ 个非零格子（1, 2, ..., p-1）之后，第 $ p $ 步才回到 1。
- 也就是说，走 $ p-1 $ 步时，你正好落在 1 号格子。

数学上，这个“走 $ a $ 步”就是“乘以 $ a $ 模 $ p $”。走 $ p-1 $ 步就是：  
$$
a \times a \times \dots \times a \quad (p-1 \text{ 个 } a)
$$
即 $ a^{p-1} $，结果在模 $ p $ 下等于 1。

`例`加深理解的例子

**例 1**：$ p = 7, a = 3 $

计算 $ 3^k \bmod 7 $：
- $ 3^1 = 3 $
- $ 3^2 = 9 \equiv 2 $
- $ 3^3 = 6 \equiv 6 $
- $ 3^4 = 18 \equiv 4 $
- $ 3^5 = 12 \equiv 5 $
- $ 3^6 = 15 \equiv 1 $  ← 看，$ 3^{7-1} \equiv 1 \pmod{7} $

**例 2**：$ p = 5, a = 4 $

- $ 4^1 \equiv 4 $
- $ 4^2 = 16 \equiv 1 $
- $ 4^3 \equiv 4 $
- $ 4^4 \equiv 1 $  ← 仍然成立，虽然这里周期是 2，但 $ p-1=4 $ 时确实是 1。

## 欧拉定理

用证明费马小定理的方法, 我们还可以证明更一般的结论一欧拉定理.

> **欧拉定理** 设 $m$ 为正整数, $a$ 为任意整数,且 $(a, m)=1$, 则$a^{\varphi(m)} \equiv 1(\bmod m),$ 其中 $\varphi(m)$ 表示 $1,2, \cdots, m$ 中与 $m$ 互素的正整数的个数.

$\varphi(m)$ 称为欧拉函数. 当 $m$ 为素数时, 从 1 到 $m$ 的整数中与 $m$ 互素的整数为 1 , $2, \cdots, m-1$, 共有 $m-1$ 个, 所以 $\varphi(m)=m-1$. 一般地, 当 $m$ 为大于 1 的整数时, 有

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

其中 $p_1, p_2, \cdots, p_k$ 为 $m$ 的所有互异的素因数.
一般情形 $\varphi(m)$ 的表达式的证明, 略.

`例` 计算 $\varphi$（36）。
解： $36=2^2 \cdot 3^2$ ，因此

$$
\varphi(36)=36\left(1-\frac{1}{2}\right)\left(1-\frac{1}{3}\right)=12
$$

我们不妨验证一下：
从 1 到 35 共有 35 个数。这 35 个数中，恰有 $1,5,7,11,13,17,19,23,25,29,31,35$ 与 $36$ 五素．共有 12 个数与 36 互素．可见 $\varphi(36)=12$ ．

下面我们给出欧拉定理的证明.
证明: 记 $\varphi(m)=r$, 并用 $a_1, a_2, \cdots, a_r$ 表示 $1,2,3, \cdots, m$ 中所有与 $m$ 互素的整数.

因为 $(a, m)=1$, 且 $a_1, a_2, \cdots, a_r$ 与 $m$ 均互素, 所以 $a a_1, a a_2, \cdots, a a_r$ 与 $m$ 均是互素的 (为什么?). 从而它们分属于模 $m$ 的 $r$ 个剩余类 $\left[a_1\right],\left[a_2\right], \cdots,\left[a_r\right]$. 由同余的性质 1 可得:

$$
a^r a_1 a_2 \cdots a_r \equiv a_1 a_2 \cdots a_r(\bmod m) .
$$

又因为 $a_1, a_2, \cdots, a_r$ 均与 $m$ 互素, 由同余的性质 2 可得 $a^r \equiv 1(\bmod m)$, 即

$$
a^{\varphi(m)} \equiv 1(\bmod m) \text {. }
$$

在欧拉定理中, 如果 $m$ 为素数, 此时 $\varphi(m)=m-1$, 那么我们得到了费马小定理. 费马小定理是欧拉定理的特例.
欧拉定理和费马小定理有许多重要的应用, 利用它们可以简化许多计算.

### 理解：欧拉定理

`例`更一般的“循环规律”
我们可以沿用之前的“钟表”比喻，但现在钟表上的格子数可以是任意 $ n $，不一定是质数。

- 钟表有 $ n $ 个格子，编号 $ 0, 1, 2, \dots, n-1 $。
- 但只有那些与 $ n $ 互质的数（共 $ \varphi(n) $ 个）在“乘法世界”里扮演角色。
- 如果你从 1 出发，每次乘以 $ a $（其中 $ a $ 与 $ n $ 互质），你只会经过那些与 $ n $ 互质的格子。
- 因为互质的数在模 $ n $ 乘法下构成一个群，元素个数是 $ \varphi(n) $。
- 所以当你连续乘 $ \varphi(n) $ 次 $ a $ 后，你必定回到起点 1。

这就是：
$$
a^{\varphi(n)} \equiv 1 \pmod{n}
$$

`例`例子说明

**例 1**：$ n = 8, a = 3 $

- 先求 $ \varphi(8) $：与 8 互质的数有 1, 3, 5, 7，所以 $ \varphi(8) = 4 $。
- 检查 $ 3^4 \bmod 8 $：
  - $ 3^1 = 3 $
  - $ 3^2 = 9 \equiv 1 \pmod{8} $
  - $ 3^3 \equiv 3 $
  - $ 3^4 \equiv 1 $  
  确实 $ 3^4 \equiv 1 \pmod{8} $。

**例 2**：$ n = 9, a = 2 $

- $ \varphi(9) = 6 $（与 9 互质：1,2,4,5,7,8）。
- 计算 $ 2^k \bmod 9 $：
  - $ 2^1 = 2 $
  - $ 2^2 = 4 $
  - $ 2^3 = 8 $
  - $ 2^4 = 16 \equiv 7 $
  - $ 2^5 = 14 \equiv 5 $
  - $ 2^6 = 10 \equiv 1 $  ← 看，$ 2^6 \equiv 1 \pmod{9} $，而 $ \varphi(9)=6 $。

## 例题

`例`求 $13^{2004}$ 除以 17 的余数.
分析: 遇到有关带指数的被除数的问题, 我们首先考虑运用同余、互素以及欧拉定理或费马小定理, 降次使被除数变小, 进而求出余数.
解: 容易知道 17 为素数, 且 $(13,17)=1$, 由费马小定理可知

$$
13^{17-1}=13^{16} \equiv 1(\bmod 17) \text {. }
$$

又因为 $2004=16 \times 125+4$, 且 13 为素数, 所以

$$
13^{2004}=\left(13^{16}\right)^{125} \times 13^4 \equiv 13^4(\bmod 17) .
$$

而 $13^4=169^2=(170-1)^2 \equiv(-1)^2=1(\bmod 17)$ ，
因此 $13^{2004} \equiv 1(\bmod 17)$, 即
$13^{2004}$ 除以 17 的余数为 1 .

`例`求使 $5^m \equiv 1(\bmod 21)$ 成立的最小正整数 $m$.
分析: $5^m \equiv 1(\bmod 21)$ 与欧拉定理的形式类似, 而且 $(5,21)=1, \varphi(21)$ 容易求出. 我们考虑使用欧拉定理.

解: 因为 $(5,21)=1$, 且 $\varphi(21)=12$ (即 $1,2, \cdots, 20$ 中与 21 互素的数有 12 个),由欧拉定理有

$$
5^{12} \equiv 1(\bmod 21) \text {. }
$$

显然, $m \leqslant 12$. 令 $12=m q+r$, 其中 $0 \leqslant r<m$, 则有

$$
5^{12}=5^{m q}+r=\left(5^m\right)^q \times 5^r,
$$

所以 $1 \equiv 5^r(\bmod 21)$.
由 $m$ 是使同余式成立的最小正整数知 $r=0$, 从而 $m \mid 12$. 检验 12 的正因数 $1,2,3$, $4,6,12$, 我们发现

$$
\begin{aligned}
& 5^1 \equiv 5(\bmod 21), 5^2 \equiv 4(\bmod 21), \\
& 5^3=20(\bmod 21), 5^4 \equiv 16(\bmod 21), \\
& 5^6 \equiv 1(\bmod 21),
\end{aligned}
$$

因此, 最小正整数 $m$ 为 6 .

由上面的例子不难看出, 费马小定理和欧拉定理在解决较大数的整除或同余问题时具有重要的作用.

`例` 证明 $15 \mid\left(49^4-1\right)$ 。
证明：由 $\varphi(15)=\varphi(3) \varphi(5)=2 \times 4=8$ 及欧拉定理即得

$$
49^4 \equiv 7^8 \equiv 7^{\varphi(15)} \equiv 1( mod 15)
$$

所以 $15 \mid\left(49^4-1\right)$ ．

`例`  $7^{362}$ 的末两位数是什么？
解：由 $\varphi(100)=100\left(1-\frac{1}{2}\right)\left(1-\frac{1}{5}\right)=40$ 及欧拉定理即得

$$
7^{40} \equiv 1(\bmod 100)
$$

又由 $362=9 \times 40+2$ 可得

$$
7^{362} \equiv 7^2 \equiv 49(\bmod 100)
$$

所以 $7^{362}$ 的末两位数是 49 ．

`例` 今天星期一，问这以后的第$47^{37}$天是星期几？
解：由费马小定理知

$$
47^6 \equiv 1(\bmod 7) .
$$

又由 $37=6 \times 6+1$ 可得

$$
47^{37} \equiv 47 \equiv 5(\bmod 7)
$$

所以是星期六．

其他版本
【高等代数】Euler 函数、费马小定理与剩余定理

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：剩余系与欧拉函数

下一篇：一次同余方程

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