最后更新: 2025-10-20 05:42 查看: 611 次纠错评论(0) 课件开VIP

课外阅读：费马小定理

## 费马小定理
费马小定理是指对于任意质数 $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)$ ，定理得证。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：课外阅读：费马大定理

下一篇：课外阅读：哥德巴赫猜想与孪生素数

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