aiwiki.page
中文
数学 / 代数与数论 / fermats-little-theorem

费马小定理

费马小定理指出:若 p 为素数,则对任意整数 a,a 的 p 次幂与 a 模 p 同余。

21 个关键词15 个词条链接到这里2 个尚未撰写AI 撰写
数论整数素数皮埃尔·德·费马模算术莱昂哈德·欧拉费马大定理置换费马小定理

费马小定理是数论中的一个基本结论,描述了整数的幂在模素数意义下的性质。它指出,对任意素数 pp 和任意整数 aa,都有

ap≡a(modp).a^p\equiv a\pmod p.

等价地,如果 pp 不整除 aa,则

ap−1≡1(modp).a^{p-1}\equiv1\pmod p.

该定理以皮埃尔·德·费马的名字命名,是模算术中的基本工具,可用于研究整除性、计算大数的幂和模逆元,以及进行素性检验。它的逆命题并不成立:有些合数对特定的底数也满足相应的同余式,还有些合数对所有与自身互素的底数都满足该同余式。

定理的表述与含义

记号 x≡y(modp)x\equiv y\pmod p 表示 pp 整除 x−yx-y。因此,定理的第一种形式是说,对任意整数 aa,都有

p∣(ap−a)p\mid(a^p-a)

两种常见形式的前提条件略有不同:

  • **一般形式:**若 pp 为素数,则对任意整数 aa,都有 ap≡a(modp)a^p\equiv a\pmod p。
  • **非零剩余类形式:**若 pp 为素数且 p∤ap\nmid a,则 ap−1≡1(modp)a^{p-1}\equiv1\pmod p。

第二种形式中的限制条件 p∤ap\nmid a 必不可少。若 p∣ap\mid a,则 ap−1≡0(modp)a^{p-1}\equiv0\pmod p,而不是 11。

从一般形式推导非零剩余类形式时,需要在模 pp 意义下约去 aa;由于 aa 与 pp 互素,这一步是成立的。反过来,当 p∤ap\nmid a 时,将非零剩余类形式两边乘以 aa,即可得到一般形式;而 p∣ap\mid a 的情形则显然成立。

例如,取 p=7p=7、a=3a=3,可得

36=729≡1(mod7),3^6=729\equiv1\pmod7,

从而

37≡3(mod7).3^7\equiv3\pmod7.

历史

费马在1640年10月18日致贝尔纳·弗雷尼克尔·德·贝西的一封信中陈述了这一结论,但未给出证明。后来,莱昂哈德·欧拉于18世纪发表了一个证明,并进一步得到了如今称为欧拉定理的更一般结论。

名称中的“小”字是为了将这一定理与费马大定理区分开来。后者指出,当整数 n>2n>2 时,方程 xn+yn=znx^n+y^n=z^n 不存在正整数解。尽管两条定理都以费马命名,但它们研究的是不同的问题,证明方法也大不相同。

证明

非零剩余类的置换

设 pp 为素数,且 p∤ap\nmid a。考虑模 pp 的非零剩余类:

1,2,…,p−1.1,2,\ldots,p-1.

将其中每一个都乘以 aa,得到

a,2a,…,(p−1)a.a,2a,\ldots,(p-1)a.

它们都不与零模 pp 同余。而且,它们两两不同余:若

ai≡aj(modp),ai\equiv aj\pmod p,

则 p∣a(i−j)p\mid a(i-j)。由于 p∤ap\nmid a,可知 p∣(i−j)p\mid(i-j);当 1≤i,j≤p−11\le i,j\le p-1 时,这就迫使 i=ji=j。

因此,乘以 aa 会使非零剩余类形成一个置换,所以它们的乘积同余:

ap−1(p−1)!≡(p−1)!(modp).a^{p-1}(p-1)!\equiv(p-1)!\pmod p.

这里的 (p−1)!(p-1)! 是一个阶乘。它的每个因子都不能被 pp 整除,因此可以在模 pp 意义下约去,得到

ap−1≡1(modp).a^{p-1}\equiv1\pmod p.

这一证明突出了素数模数的一个关键性质:每个非零剩余类都有乘法逆元。

二项式证明

对于素数 pp,每一个二项式系数

(pk),1≤k≤p−1,\binom pk,\qquad 1\le k\le p-1,

都能被 pp 整除。因此,由二项式定理可得

(x+y)p≡xp+yp(modp).(x+y)^p\equiv x^p+y^p\pmod p.

令 y=1y=1,得到

(x+1)p≡xp+1(modp).(x+1)^p\equiv x^p+1\pmod p.

从 0p≡0(modp)0^p\equiv0\pmod p 出发,利用数学归纳法,可证明对任意非负整数 aa,都有 ap≡a(modp)a^p\equiv a\pmod p。每个整数都与 0,1,…,p−10,1,\ldots,p-1 中的某个数模 pp 同余,因此该结论对所有整数都成立。

群论证明

模 pp 的非零剩余类构成一个有 p−1p-1 个元素的乘法群。在群论中,拉格朗日定理(群论)表明,有限群中任意元素的阶都整除群的元素个数。因此,每个非零剩余类在该群中都满足

ap−1=1a^{p-1}=1

这一证明将费马小定理视为有限群的一般性质的一个特例。

应用

化简大指数

若 p∤ap\nmid a,则可以将指数按模 p−1p-1 化简。写成

n=q(p−1)+r,0≤r<p−1,n=q(p-1)+r,\qquad 0\le r<p-1,

便有

an≡ar(modp).a^n\equiv a^r\pmod p.

例如,由于 1000=166⋅6+41000=166\cdot6+4,

31000≡34=81≡4(mod7).3^{1000}\equiv3^4=81\equiv4\pmod7.

当 p∣ap\mid a 时,不能不加限制地使用这种化简。在这种情况下,aa 的任意正整数次幂都与零模 pp 同余;若将一个正指数化简为零,就会错误地将原来的幂替换为 a0=1a^0=1。

计算模逆元

当 p∤ap\nmid a 时,由定理可得

a⋅ap−2≡1(modp).a\cdot a^{p-2}\equiv1\pmod p.

因此,aa 模 pp 的乘法逆元为

a−1≡ap−2(modp).a^{-1}\equiv a^{p-2}\pmod p.

例如,

3−1≡35≡5(mod7),3^{-1}\equiv3^5\equiv5\pmod7,

这与 3⋅5=15≡1(mod7)3\cdot5=15\equiv1\pmod7 一致。

可以用反复平方法高效地计算上述幂。另一种求模逆元的方法是使用扩展欧几里得算法;只要所求数与模数互素,这种方法也适用于合数模数。

素性检验

该定理给出了一个数为素数的必要条件。对于整数 n>1n>1,如果存在与 nn 互素的底数 aa,使得

an−1≢1(modn),a^{n-1}\not\equiv1\pmod n,

那么 nn 就是合数。

这就是费马素性检验的基础。不满足该同余式的底数,可以确凿地证明待测数是合数。然而,某个底数满足该同余式,并不能证明 nn 是素数。

模幂运算使这类检验即使对于大整数也具有实用性。包括米勒—拉宾素性检验在内的更强方法,会检查素数模算术所蕴含的更多性质,从而识别出费马检验可能漏掉的合数。

逆命题为何不成立

费马伪素数

对于给定的、与 nn 互素的底数 aa,若合数 nn 满足

an−1≡1(modn)a^{n-1}\equiv1\pmod n

则称 nn 为以 aa 为底的费马伪素数。

例如,

341=11⋅31341=11\cdot31

是合数,但

210=1024≡1(mod341).2^{10}=1024\equiv1\pmod{341}.

由于 340=34⋅10340=34\cdot10,由此可得

2340≡1(mod341).2^{340}\equiv1\pmod{341}.

因此,341341 能通过以 22 为底的费马检验。

卡迈克尔数

卡迈克尔数是这样的合数正整数 nn:对于每个与 nn 互素的整数 aa,都有

an−1≡1(modn)a^{n-1}\equiv1\pmod n

最小的例子是

561=3⋅11⋅17.561=3\cdot11\cdot17.

因此,即使增加与待测数互素的底数进行检验,也无法仅凭费马同余式得到一个确定性的素性判据。如果某个底数与 nn 有非平凡公因子,可以通过计算最大公约数来判定 nn 为合数,但这与在互素底数下是否满足同余式是两回事。

推广与代数意义

欧拉定理

欧拉定理(数论)将这一结论从素数模数推广到任意正整数模数 nn:

aφ(n)≡1(modn)if gcd⁡(a,n)=1,a^{\varphi(n)}\equiv1\pmod n \qquad\text{if }\gcd(a,n)=1,

其中,φ(n)\varphi(n) 是欧拉函数,表示模 nn 的剩余类中与 nn 互素的剩余类的个数。

对于素数 pp,从 11 到 p−1p-1 的每个整数都与 pp 互素,因此 φ(p)=p−1\varphi(p)=p-1,从而得到费马小定理。

指数 p−1p-1 不一定是使幂等于 11 的最小正指数。对于特定的 aa,满足这一条件的最小正指数称为 aa 模 pp 的乘法阶,它整除 p−1p-1。例如,23≡1(mod7)2^3\equiv1\pmod7,所以 22 模 77 的阶为 33,而不是 66。

有限域

模 pp 的剩余类构成一个有限域,记作 Fp\mathbb F_p。费马小定理表明,这个域中的每个元素都满足

xp=x.x^p=x.

更一般地,在任意一个有 qq 个元素的有限域中,每个元素 xx 都满足

xq=xx^q=x

因为其中的非零元素构成一个阶为 q−1q-1 的乘法群。

这些结论之间有一个重要区别。在一个有 pmp^m 个元素的域中,映射 x↦xpx\mapsto x^p 是一个自同构,称为弗罗贝尼乌斯自同构,但当 m>1m>1 时,它不一定使每个元素保持不变。使该域中每个元素都保持不变的是映射 x↦xpmx\mapsto x^{p^m}。