最后更新: 2025-03-08 08:38 查看: 398 次反馈刷题

费马小定理

## 费马小定理
费马小定理是指对于任意质数 $p$ 及任意正整数 $a$ 而言， $a$ 的 $p$ 次方减 $a$ 可为 $p$ 除尽，或当 $a$ 与 $p$ 互质时， $a$ 的 $p-1$ 次方除以 $p$ 的余数为1。

费马小定理的可推广至对任意互质正整数的 $a$ 和 $m$ 上，对任意的 $a$ 而言，当 $a$ 与 $m$ 互质时， $a$ 的 $\varphi(m)$ 次方除以 $m$ 的余数为 1 ，其中 $\varphi(m)$ 是不大于 $m$ 且与 $m$ 互质的正整数个数。

## 费马小定理的作用
考虑同余式
$$
-6^{22}   \equiv 1(\bmod 23)
$$

这说明数 $6^{22}-1$ 是 23 的倍数．如果不用费马小定理验证这个事实，则必须算出 $6^{22}$ 减 1 再除以 23 ．下面是所得结果：

$$
6^{22}-1=23 \cdot 5722682775750745
$$

类似地，为直接验证 $73^{100} \equiv 1(\bmod 101)$ ，必须计算 $73^{100}-1$ 。不幸的是， $73^{100}-1$ 有 187 位数．注意这个例子仅使用 $p=101$ ，这是比较小的素数．因此，费马小定理描述了有关大数的一个令人惊讶的事实．
我们可使用费马小定理简化计算．例如，为计算 $2^{35}(\bmod 7)$ ，可利用 $2^6 \equiv 1(\bmod 7)$ 。所以记 $35=6 \cdot 5+5$ ，使用指数律计算

$$
2^{35}=2^{6 \cdot 5+5}=\left(2^6\right)^5 \cdot 2^5 \equiv 1^5 \cdot 2^5 \equiv 32 \equiv 4(\bmod 7)
$$

类似地：，假设要解同余式 $x^{103} \equiv 4(\bmod 11)$ 。肯定有 $x \not \equiv 0(\bmod 11)$ ，因此由费马小定理得

$$
11 \quad i^2 \quad x^{10} \equiv 1(\bmod 11)
$$

两边自乘 10 次得 $x^{100} \equiv 1(\bmod 11)$ ，然后乘以 $x^3$ 得 $x^{103} \equiv x^3(\bmod 11)$ 。要解原同余式，正好需要解 $x^3 \equiv 4(\bmod 11)$ ．通过连续尝试 $x=1, x=2, \cdots$ ，可解这个同余式．这样

$$
\begin{array}{|l|l|l|l|l|l|l|l|l|l|l|l|}
\hline x(\bmod 11) & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\
\hline x^3(\bmod 1 \cdot 1) \cdot & 0 & 1 & 8 & 5 & 9 & 4 & 7 & 2 & 6 & 3 & 10 \\
\hline
\end{array}
$$

因此同余式 $x^{103} \equiv 4(\bmod 11)$ 有解 $x \equiv 5(\bmod 11)$ 。

更多例子参考 [初等数论教材费马小定理](https://kb.kmath.cn/kbase/detail.aspx?id=796)

## 证明

**此处所给之证明可能不严谨，或有所疏漏，还请大家校验与修正**

以下证明对质数的状况。

若 $p$ 为质数，则 $1 、 2 、 3 \cdots p-1$ 等数皆与 $p$ 互质，且 $\{1,2,3, \ldots \ldots ., p-1\}$ 构成模 $p$ 的一个完全剩余系，对于任意与 $p$ 互质的 $x$ 而言， $x 、 2 x 、 3 x$...等也与 $p$ 互质，且 $\{x, 2 x, 3 x, \ldots \ldots . .,(p-1) x\}$ 亦构成模 $p$ 的一个完全剩余系，因此，
$\prod_{i=1}^{p-1} x i \equiv \prod_{i=1}^N i(\bmod m)$ ，故 $x^{p-1} \prod_{i=1}^N i \equiv \prod_{i=1}^N i(\bmod m)$ ，而 $\left(\prod_{i=1}^N i, p\right)=1$ ，故可做除法将两边的 $\prod_{i=1}^N$ 除去，故得 $x^{p-1} \equiv 1 \quad(\bmod m)$ ，定理得证。

刷题

做题，是检验是否掌握数学的唯一真理

上一篇：费马大定理

下一篇：哥德巴赫猜想与孪生素数

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