费马小定理是数论中的一个基本结论,描述了整数的幂在模素数意义下的性质。它指出,对任意素数 p 和任意整数 a,都有
ap≡a(modp).
等价地,如果 p 不整除 a,则
ap−1≡1(modp).
该定理以皮埃尔·德·费马的名字命名,是模算术中的基本工具,可用于研究整除性、计算大数的幂和模逆元,以及进行素性检验。它的逆命题并不成立:有些合数对特定的底数也满足相应的同余式,还有些合数对所有与自身互素的底数都满足该同余式。
定理的表述与含义
记号 x≡y(modp) 表示 p 整除 x−y。因此,定理的第一种形式是说,对任意整数 a,都有
p∣(ap−a)
两种常见形式的前提条件略有不同:
- **一般形式:**若 p 为素数,则对任意整数 a,都有 ap≡a(modp)。
- **非零剩余类形式:**若 p 为素数且 p∤a,则 ap−1≡1(modp)。
第二种形式中的限制条件 p∤a 必不可少。若 p∣a,则 ap−1≡0(modp),而不是 1。
从一般形式推导非零剩余类形式时,需要在模 p 意义下约去 a;由于 a 与 p 互素,这一步是成立的。反过来,当 p∤a 时,将非零剩余类形式两边乘以 a,即可得到一般形式;而 p∣a 的情形则显然成立。
例如,取 p=7、a=3,可得
36=729≡1(mod7),
从而
37≡3(mod7).
历史
费马在1640年10月18日致贝尔纳·弗雷尼克尔·德·贝西的一封信中陈述了这一结论,但未给出证明。后来,莱昂哈德·欧拉于18世纪发表了一个证明,并进一步得到了如今称为欧拉定理的更一般结论。
名称中的“小”字是为了将这一定理与费马大定理区分开来。后者指出,当整数 n>2 时,方程 xn+yn=zn 不存在正整数解。尽管两条定理都以费马命名,但它们研究的是不同的问题,证明方法也大不相同。
证明
非零剩余类的置换
设 p 为素数,且 p∤a。考虑模 p 的非零剩余类:
1,2,…,p−1.
将其中每一个都乘以 a,得到
a,2a,…,(p−1)a.
它们都不与零模 p 同余。而且,它们两两不同余:若
ai≡aj(modp),
则 p∣a(i−j)。由于 p∤a,可知 p∣(i−j);当 1≤i,j≤p−1 时,这就迫使 i=j。
因此,乘以 a 会使非零剩余类形成一个置换,所以它们的乘积同余:
ap−1(p−1)!≡(p−1)!(modp).
这里的 (p−1)! 是一个阶乘。它的每个因子都不能被 p 整除,因此可以在模 p 意义下约去,得到
ap−1≡1(modp).
这一证明突出了素数模数的一个关键性质:每个非零剩余类都有乘法逆元。
二项式证明
对于素数 p,每一个二项式系数
(kp),1≤k≤p−1,
都能被 p 整除。因此,由二项式定理可得
(x+y)p≡xp+yp(modp).
令 y=1,得到
(x+1)p≡xp+1(modp).
从 0p≡0(modp) 出发,利用数学归纳法,可证明对任意非负整数 a,都有 ap≡a(modp)。每个整数都与 0,1,…,p−1 中的某个数模 p 同余,因此该结论对所有整数都成立。
群论证明
模 p 的非零剩余类构成一个有 p−1 个元素的乘法群。在群论中,拉格朗日定理(群论)表明,有限群中任意元素的阶都整除群的元素个数。因此,每个非零剩余类在该群中都满足
这一证明将费马小定理视为有限群的一般性质的一个特例。
应用
化简大指数
若 p∤a,则可以将指数按模 p−1 化简。写成
n=q(p−1)+r,0≤r<p−1,
便有
an≡ar(modp).
例如,由于 1000=166⋅6+4,
31000≡34=81≡4(mod7).
当 p∣a 时,不能不加限制地使用这种化简。在这种情况下,a 的任意正整数次幂都与零模 p 同余;若将一个正指数化简为零,就会错误地将原来的幂替换为 a0=1。
计算模逆元
当 p∤a 时,由定理可得
a⋅ap−2≡1(modp).
因此,a 模 p 的乘法逆元为
a−1≡ap−2(modp).
例如,
3−1≡35≡5(mod7),
这与 3⋅5=15≡1(mod7) 一致。
可以用反复平方法高效地计算上述幂。另一种求模逆元的方法是使用扩展欧几里得算法;只要所求数与模数互素,这种方法也适用于合数模数。
素性检验
该定理给出了一个数为素数的必要条件。对于整数 n>1,如果存在与 n 互素的底数 a,使得
an−1≡1(modn),
那么 n 就是合数。
这就是费马素性检验的基础。不满足该同余式的底数,可以确凿地证明待测数是合数。然而,某个底数满足该同余式,并不能证明 n 是素数。
模幂运算使这类检验即使对于大整数也具有实用性。包括米勒—拉宾素性检验在内的更强方法,会检查素数模算术所蕴含的更多性质,从而识别出费马检验可能漏掉的合数。
逆命题为何不成立
费马伪素数
对于给定的、与 n 互素的底数 a,若合数 n 满足
an−1≡1(modn)
则称 n 为以 a 为底的费马伪素数。
例如,
341=11⋅31
是合数,但
210=1024≡1(mod341).
由于 340=34⋅10,由此可得
2340≡1(mod341).
因此,341 能通过以 2 为底的费马检验。
卡迈克尔数
卡迈克尔数是这样的合数正整数 n:对于每个与 n 互素的整数 a,都有
an−1≡1(modn)
最小的例子是
561=3⋅11⋅17.
因此,即使增加与待测数互素的底数进行检验,也无法仅凭费马同余式得到一个确定性的素性判据。如果某个底数与 n 有非平凡公因子,可以通过计算最大公约数来判定 n 为合数,但这与在互素底数下是否满足同余式是两回事。
推广与代数意义
欧拉定理
欧拉定理(数论)将这一结论从素数模数推广到任意正整数模数 n:
aφ(n)≡1(modn)if gcd(a,n)=1,
其中,φ(n) 是欧拉函数,表示模 n 的剩余类中与 n 互素的剩余类的个数。
对于素数 p,从 1 到 p−1 的每个整数都与 p 互素,因此 φ(p)=p−1,从而得到费马小定理。
指数 p−1 不一定是使幂等于 1 的最小正指数。对于特定的 a,满足这一条件的最小正指数称为 a 模 p 的乘法阶,它整除 p−1。例如,23≡1(mod7),所以 2 模 7 的阶为 3,而不是 6。
有限域
模 p 的剩余类构成一个有限域,记作 Fp。费马小定理表明,这个域中的每个元素都满足
更一般地,在任意一个有 q 个元素的有限域中,每个元素 x 都满足
因为其中的非零元素构成一个阶为 q−1 的乘法群。
这些结论之间有一个重要区别。在一个有 pm 个元素的域中,映射 x↦xp 是一个自同构,称为弗罗贝尼乌斯自同构,但当 m>1 时,它不一定使每个元素保持不变。使该域中每个元素都保持不变的是映射 x↦xpm。