最后更新: 2025-06-21 09:34 查看: 276 次反馈同步训练

费马小定理与欧拉定理

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

在模 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 {. }
$$

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

## 欧拉定理

> **欧拉定理** 设 $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],\

免费注册看余下 50%

非VIP会员每天15篇文章，开通VIP 无限制查看

上一篇：剩余系

下一篇：一次同余方程

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