日期: 2023-11-09 18:44 查看: 151 次编辑

费马小定理与欧拉定理

我们发现, 探究中的三个等式都是成立的.
事实上, 我们还可以进一步探究得知, 在模 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(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$, 那么我们得到了费马小定理. 费马小定理是欧拉定理的特例.
欧拉定理和费马小定理有许多重要的应用, 利用它们可以简化许多计算.
例 3 求 $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 .
例 4 求使 $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 .

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

上一篇：负元与逆元

下一篇：一次同余方程

本文对您是否有用？有用 (0) 无用 (0) 赞助我们

0 篇笔记写笔记

更多笔记