Fermat 小定理

此页面尚不符合香蕉空间的百科写作风格, 并需要改进. 请编辑者参照已有的与之内容相近的条目, 以及香蕉空间:写作指引的要求, 对此页面进行修改. 具体问题如下:

• 行文风格不符合香蕉空间: 写作指引的要求.
• 术语使用不符合香蕉空间: 术语规范.

Fermat 小定理是初等数论中的核心定理之一, 由皮埃尔·德·费马在 17 世纪提出. 它刻画了素数模数下的幂运算性质, 模运算的理论基础.
Fermat 小定理大致是说, 假如 a 是一个整数, p 是一个质数, 那么 $a^p-a$ 是 p 的倍数.

1定义

定理 1.1 (费马小定理). 设 $p$ 为素数, $a$ 为整数且满足 $\gcd (a,p)=1$ (即 $a$ 与 $p$ 互质) , 则: $$a^{p-1}\equiv 1(\mathrm{mod}p)$$

定理 1.2 (欧拉定理). 推广到任意正整数模数 $n$: 若 $\gcd (a,n)=1$, 则: $$a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$$其中 $\varphi (n)$ 为欧拉函数, 表示小于 $n$ 且与 $n$ 互质的正整数的个数.

2证明

组合学证明

证明. 考虑集合 $S=\{a,2a,3a,\dots ,(p-1)a\}$. 由于 $a$ 与 $p$ 互质, 模 $p$ 下这些元素两两不同余且均不为零. 因此: $$\prod _{k=1}^{p-1}ka\equiv \prod _{k=1}^{p-1}k(\mathrm{mod}p)$$即: $$a^{p-1}\cdot (p-1)!\equiv (p-1)!(\mathrm{mod}p)$$因 $(p-1)!$ 与 $p$ 互质, 两边可约去, 得 $a^{p-1}\equiv 1(\mathrm{mod}p)$.

$\square$

群论证明

证明. 模 $p$ 的缩剩余系 $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$ 构成一个 $p-1$ 阶乘法群. 根据拉格朗日定理, 任意元素 $a$ 的阶整除群阶, 故 $a^{p-1}\equiv 1(\mathrm{mod}p)$.

$\square$

3例子

例 3.1 (数值验证). 取 $p=7$ (素数) , $a=3$ (满足 $\gcd (3,7)=1$) . 计算: $$3^{7-1}=3^6=729\equiv 1(\mathrm{mod}7)(\text{因 }729=7\times 104+1)$$

例 3.2 (简化计算). 求 $2^{2024}\mathrm{mod}11$. 由于 $11$ 是素数且 $\gcd (2,11)=1$, 根据费马小定理: $$2^{10}\equiv 1(\mathrm{mod}11)\Rightarrow 2^{2024}=2^{10\times 202+4}\equiv 1^{202}\cdot 2^4=16\equiv 5(\mathrm{mod}11)$$

4应用

•	素性检验: 费马素性测试 (尽管存在伪素数如卡迈克尔数) .
•	RSA 加密: 用于生成公钥与私钥的逆元计算.
•	多项式同余: 快速化简高次多项式模素数表达式.

5推广

AKS 素性检测算法作为 Fermat 小定理的推广, 适用于任意整数 n 的素性判断.

引理 5.1. 当且仅当对任意 (或某个) 与 n 互质的 a, 多项式同余式$$(x-a{)}^n\equiv x^n-a(\mathrm{mod}n)$$成立时, 整数 $n\ge 2$ 为素数

证明. 根据 Freshman 之梦定理, n 的素性等价于对所有 (或某个) a, 有$$(x-a{)}^n\equiv x^n-a^n(\mathrm{mod}n)$$当 $n$ 为素数时, 由 Fermat 小定理可得$$a^n\equiv a(\mathrm{mod}n)$$从而完成约简

$\square$

设 $r$ 为整数, $a$ 为与 $r$ 互质的整数, 定义 ${\mathrm{ord}}_r(a)$ 为 $a$ 模 $r$ 的乘法阶记 $\log n$ 为 $n$ 的二进制对数, $\varphi$ 表示欧拉总计函数 (即 $\varphi (r)表示环\mathbb{Z}/(r)中单位元的个数$)

定理 5.2. 对给定 $n$, 设 $r$ 为满足 ${\mathrm{ord}}_r(n)>(\log n{)}^2$ 的最小正整数, 则 $n$ 为素数当且仅当满足以下条件之一:

$$1.n\le r,且对于任意1\le a\le r,\gcd (a,n)=1或\gcd (a,n)=n$$

$$2.r<n,且对任意满足1\le a\le \sqrt{\varphi (r)}\cdot \log n的整数a，多项式同余式$$

$$(x-a{)}^n\equiv x^n-a(\mathrm{mod}{x}^r-1,n)$$成立.

6参考文献

•	G. H. Hardy, E. M. Wright (2008). An Introduction to the Theory of Numbers, 6thed. Oxford University Press.
•	Leonhard Euler (1736). “Theorematum quorundam ad numeros primos spectantium demonstratio”. Commentarii academiae scientiarum Petropolitanae, 141–146.
•	Neal Koblitz (1987). A Course in Number Theory and Cryptography. Springer.

7相关概念

术语翻译

Fermat 小定理 • 英文 Fermat’s little theorem • 德文 Fermats kleines Theorem • 法文 Petit théorème de Fermat • 古希腊文 Το μικρό θεώρημα του Φερμά