aiwiki.page
中文
数学 / 代数与数论 / eulers-theorem-number-theory

欧拉定理(数论)

欧拉定理指出,若整数a与正整数n互素,则a的φ(n)次幂模n同余于1,其中φ为欧拉函数。

17 个关键词6 个词条链接到这里2 个尚未撰写AI 撰写
数论模算术欧拉函数莱昂哈德·欧拉费马小定理最大公约数素数置换欧拉定理(…

欧拉定理是数论中的一项基本结果,描述了模算术中整数幂的性质。该定理指出,若 n≥2n\geq 2 为整数,且整数 aa 与 nn 互素,则

aφ(n)≡1(modn),a^{\varphi(n)}\equiv 1\pmod n,

其中,φ(n)\varphi(n) 为欧拉函数,表示从 11 到 nn 的整数中与 nn 互素的整数个数。该定理以莱昂哈德·欧拉的名字命名,是费马小定理的推广,为化简大指数、计算模逆元以及理解RSA密码的代数原理提供了基础。

定理表述与术语

两个整数的最大公约数为 11 时,称它们互素。因此,欧拉定理的前提是

gcd⁡(a,n)=1.\gcd(a,n)=1.

结论 aφ(n)≡1(modn)a^{\varphi(n)}\equiv 1\pmod n 表示 nn 整除 aφ(n)−1a^{\varphi(n)}-1。等价地说,aφ(n)a^{\varphi(n)} 除以 nn 的余数为 11。

欧拉函数定义为

φ(n)=#{k:1≤k≤n, gcd⁡(k,n)=1}.\varphi(n)= \#\{k:1\leq k\leq n,\ \gcd(k,n)=1\}.

若 nn 的不同素因子为 p1,…,prp_1,\ldots,p_r,则

φ(n)=n∏i=1r(1−1pi).\varphi(n)=n\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right).

特别地,对于素数 pp 和整数 k≥1k\geq 1,有

φ(p)=p−1,φ(pk)=pk−1(p−1).\varphi(p)=p-1, \qquad \varphi(p^k)=p^{k-1}(p-1).

例如,11 到 1010 之间与 1010 互素的整数为 1,3,7,91,3,7,9,因此 φ(10)=4\varphi(10)=4。由于 33 与 1010 互素,根据欧拉定理,

34=81≡1(mod10).3^4=81\equiv 1\pmod {10}.

互素这一限制条件不可缺少。若 gcd⁡(a,n)>1\gcd(a,n)>1,则 aa 与 nn 的某个公共素因子会整除 aa 的每个正整数次幂,因此这些幂都不可能模 nn 同余于 11。

初等证明

模 nn 的简化剩余系由所有与 nn 互素的同余类各取一个代表元组成。将这样的一个剩余系记为

r1,r2,…,rφ(n).r_1,r_2,\ldots,r_{\varphi(n)}.

若 gcd⁡(a,n)=1\gcd(a,n)=1,则乘以 aa 只会使这些同余类重新排列。事实上,每个 ariar_i 仍与 nn 互素,且由

ari≡arj(modn)ar_i\equiv ar_j\pmod n

可得

ri≡rj(modn),r_i\equiv r_j\pmod n,

因为与模数互素的因子可以约去。因此,乘以 aa 在这些简化剩余类上诱导了一个置换。

于是,它们的乘积满足

(ar1)(ar2)⋯(arφ(n))≡r1r2⋯rφ(n)(modn).(ar_1)(ar_2)\cdots(ar_{\varphi(n)}) \equiv r_1r_2\cdots r_{\varphi(n)} \pmod n.

提取 aa 的幂,得到

aφ(n)r1r2⋯rφ(n)≡r1r2⋯rφ(n)(modn).a^{\varphi(n)}r_1r_2\cdots r_{\varphi(n)} \equiv r_1r_2\cdots r_{\varphi(n)} \pmod n.

乘积 r1r2⋯rφ(n)r_1r_2\cdots r_{\varphi(n)} 与 nn 互素,因此也可以约去,从而得到

aφ(n)≡1(modn).a^{\varphi(n)}\equiv 1\pmod n.

这里能否约去因子,取决于该因子是否与模数互素,而不只是它是否非零。对于合数模数,这一区别至关重要。

群论解释

在群论中,模 nn 的可逆剩余类在乘法运算下构成一个群,记为

(Z/nZ)×.(\mathbb Z/n\mathbb Z)^\times.

它是环(数学) Z/nZ\mathbb Z/n\mathbb Z 的单位群,恰有 φ(n)\varphi(n) 个元素。

根据拉格朗日定理(群论),有限群中任一元素的阶都整除群的元素个数。因此,将 (Z/nZ)×(\mathbb Z/n\mathbb Z)^\times 中任一元素取 φ(n)\varphi(n) 次幂,都会得到单位元。这正是欧拉定理。

更具体地说,aa 模 nn 的乘法阶记为 ord⁡n(a)\operatorname{ord}_n(a),是满足

ad≡1(modn).a^d\equiv 1\pmod n.

的最小正整数 dd。当 gcd⁡(a,n)=1\gcd(a,n)=1 时,

ord⁡n(a)∣φ(n).\operatorname{ord}_n(a)\mid\varphi(n).

因此,欧拉定理给出了适用于所有可逆剩余类的通用指数,但它不一定是某个特定剩余类所对应的最小指数。

与费马小定理的关系

当模数为素数 pp 时,每个非零剩余类都可逆,且 φ(p)=p−1\varphi(p)=p-1。欧拉定理变为

ap−1≡1(modp)if p∤a,a^{p-1}\equiv 1\pmod p \qquad\text{if }p\nmid a,

这就是费马小定理。

与之等价的素数模数表述

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

对任意整数 aa 都成立,包括 pp 的倍数。

欧拉的贡献在于,用 φ(n)\varphi(n) 代替 p−1p-1,并加上互素条件,从而将素数模数下的结果推广到任意正整数模数。这一定理是欧拉在18世纪发展数论的成果之一;其现代群论表述则将它纳入了更一般的有限群理论。

应用

化简大指数

若 gcd⁡(a,n)=1\gcd(a,n)=1,将非负整数指数 mm 写成

m=qφ(n)+r,0≤r<φ(n).m=q\varphi(n)+r, \qquad 0\leq r<\varphi(n).

则

am=(aφ(n))qar≡ar(modn).a^m =\left(a^{\varphi(n)}\right)^q a^r \equiv a^r\pmod n.

例如,φ(20)=8\varphi(20)=8,且 gcd⁡(7,20)=1\gcd(7,20)=1。由于

123≡3(mod8),123\equiv 3\pmod 8,

可得

7123≡73=343≡3(mod20).7^{123}\equiv 7^3=343\equiv 3\pmod {20}.

如果底数与 nn 不互素,通常不能用这种方式将指数对 φ(n)\varphi(n) 取模。

计算模逆元

aa 模 nn 的模乘法逆元是满足

ab≡1(modn).ab\equiv 1\pmod n.

的整数 bb。这样的逆元存在,当且仅当 gcd⁡(a,n)=1\gcd(a,n)=1。由欧拉定理可得

a−1≡aφ(n)−1(modn).a^{-1}\equiv a^{\varphi(n)-1}\pmod n.

例如,由于 φ(10)=4\varphi(10)=4,

3−1≡33=27≡7(mod10).3^{-1}\equiv 3^3=27\equiv 7\pmod {10}.

这个公式在理论研究和已知欧拉函数值的情况下很有用。扩展欧几里得算法也能计算模逆元,而且不需要知道 φ(n)\varphi(n)。

RSA密码

欧拉定理是解释RSA密码系统数学原理的核心。对于不同的素数 pp 和 qq,令

n=pq,φ(n)=(p−1)(q−1).n=pq, \qquad \varphi(n)=(p-1)(q-1).

若正整数 ee 和 dd 满足

ed≡1(modφ(n)),ed\equiv 1\pmod{\varphi(n)},

则对于每个与 nn 互素的消息代表值 mm,都有

(me)d=med≡m(modn).(m^e)^d=m^{ed}\equiv m\pmod n.

对于与 nn 不互素的消息代表值,RSA也能正确还原消息,但仅凭欧拉定理无法证明这种情况。分别在模 pp 和模 qq 下应用费马小定理,再利用中国剩余定理,即可证明该结果对模 nn 的每个剩余类都成立。

这种代数上的正确性与密码学安全性并不相同;安全的加密方案除了直接进行模幂运算外,还需要其他构造。

更小的指数与局限性

卡迈克尔函数 λ(n)\lambda(n) 是使每个与 nn 互素的整数 aa 都满足

aλ(n)≡1(modn)a^{\lambda(n)}\equiv 1\pmod n

的最小正整数。它满足

λ(n)∣φ(n).\lambda(n)\mid\varphi(n).

因此,它给出的通用指数可能比欧拉函数值更小。

例如,

φ(8)=4,λ(8)=2.\varphi(8)=4, \qquad \lambda(8)=2.

每个奇数都满足 a2≡1(mod8)a^2\equiv 1\pmod 8,所以欧拉定理给出的指数 44 虽然有效,却不是最小的。对于某个特定底数,其乘法阶还可能更小。

欧拉定理也不是素性判定准则:只要满足前提条件,并使用正确的欧拉函数值,其结论对任何模数都成立。相比之下,费马型素性检验所用的同余式 an−1≡1(modn)a^{n-1}\equiv 1\pmod n,即使在 nn 为合数时也可能成立。

最后,这一定理本身并未提供一种对任意大整数高效计算 φ(n)\varphi(n) 的方法。已知素因数分解时,利用乘积公式计算很直接,但求出素因数分解在计算上可能很困难。对于RSA模数 n=pqn=pq,知道 φ(n)\varphi(n) 就能得到

p+q=n+1−φ(n),p+q=n+1-\varphi(n),

进而可将 pp 和 qq 作为方程

x2−(n+1−φ(n))x+n=0.x^2-\bigl(n+1-\varphi(n)\bigr)x+n=0.

的两个根求出。